🧩 Maximum Subarray Problem — The Ultimate Guide (Brute Force + Kadane’s Algorithm + Divide & Conquer)
The Maximum Subarray Problem is one of the most essential coding interview problems. It appears frequently in interviews for companies like FAANG, fintech giants, startups, and data engineering roles.
This problem builds your foundation in:
- Dynamic Programming
- Greedy thinking
- Divide & Conquer patterns
- Understanding how subarrays behave with positive and negative numbers
This guide explains the problem in simple terms, walks through the thought process, shows multiple approaches, and ends with clean, ready-to-use code.
Let’s dive in!
📘 Problem Statement
You are given an integer array nums.
Your task is to find the continuous subarray (not separate elements) that produces the largest sum, and return that sum.
📌 Example 1
Input:nums = [-2,1,-3,4,-1,2,1,-5,4]
Output:6
Explanation:
The subarray:
[4, -1, 2, 1]
gives the maximum sum.
Total = 4 + (-1) + 2 + 1 = 6
📌 Example 2
Input: [1]
Output: 1
📌 Example 3
Input: [5,4,-1,7,8]
Output: 23
🧠 Understanding the Problem — How to Think About It
Before solving, let’s build intuition.
✔ 1. The subarray must be continuous
We are not allowed to pick random elements; we must pick elements that are next to each other.
✔ 2. Negative numbers reduce your sum
This is the biggest challenge. Too many negative numbers will destroy your sum.
✔ 3. If your running sum becomes negative, it harms future sums
Example:
If your sum becomes -10, and the next number is 5…
Should you continue?
-10 + 5 = -5 (bad)
It’s better to start fresh from 5.
✔ 4. You must track two things
- The best sum ending at current index
- The best sum overall
These ideas lead us toward the famous Kadane’s Algorithm.
But before that, let’s explore all approaches.
.
📊 Flowchart / Diagram for Maximum Subarray (Kadane’s Algorithm)
┌────────────────────────────┐
│ Start Algorithm │
└───────────────┬────────────┘
│
▼
┌────────────────────────┐
│ Initialize: │
│ currentSum = nums[0] │
│ maxSum = nums[0] │
└─────────┬──────────────┘
│
▼
┌──────────────────────────────┐
│ Loop through array from i=1 │
└───────────────┬──────────────┘
│
▼
┌────────────────────────────────────────┐
│ For each nums[i]: │
│ currentSum = max(nums[i], │
│ currentSum + nums[i])│
└───────────────────┬────────────────────┘
│
▼
┌───────────────────────┐
│ Update maxSum = │
│ max(maxSum, │
│ currentSum) │
└───────────┬───────────┘
│
▼
┌─────────────────────────────────┐
│ Move to next element until end │
└──────────────────┬──────────────┘
│
▼
┌────────────────────────────┐
│ Return maxSum (Answer) │
└────────────────────────────┘🪜 Approach 1: Brute Force (O(n²))
💡 Idea:
Check the sum of every possible subarray and pick the maximum.
📝 Why it works:
Because you literally check all possibilities.
👎 Why it’s bad:
Too slow for large arrays (10⁵ elements).
For interviews, this will get rejected.
✔ Brute Force Code
def maxSubArray_bruteforce(nums):
max_sum = float('-inf')
for i in range(len(nums)):
current_sum = 0
for j in range(i, len(nums)):
current_sum += nums[j]
max_sum = max(max_sum, current_sum)
return max_sum
⚡ Approach 2: Kadane’s Algorithm (Optimized O(n) Solution)
This is the most efficient and most popular solution.
🎯 Intuition Behind Kadane’s Algorithm
🔥 Key observation:
At every index:
You must choose between:
- Starting a new subarray
(if the current number is better than your running sum) - Continuing the previous subarray
(if adding the current number increases the sum)
We express this as:
currentSum = max(nums[i], currentSum + nums[i])
Then update global maximum:
maxSum = max(maxSum, currentSum)
🧠 Why Does This Work?
Let’s break it down with emotions:
- If your past sum is positive, keep it (it helps you).
- If your past sum is negative, throw it away (it harms you).
This is exactly like choosing good friends (positive influence) and avoiding bad ones (negative influence).
You only keep what improves your future sum.
✔ Kadane’s Algorithm Code
def maxSubArray(nums):
current_sum = nums[0]
max_sum = nums[0]
for i in range(1, len(nums)):
current_sum = max(nums[i], current_sum + nums[i])
max_sum = max(max_sum, current_sum)
return max_sum
🔍 Step-by-Step Example (Kadane’s Algorithm)
Input:
[-2,1,-3,4,-1,2,1,-5,4]
| Index | Num | currentSum | maxSum | Explanation |
|---|---|---|---|---|
| 0 | -2 | -2 | -2 | Start |
| 1 | 1 | 1 | 1 | Better to start fresh |
| 2 | -3 | -2 | 1 | Negative pulls sum down |
| 3 | 4 | 4 | 4 | New start |
| 4 | -1 | 3 | 4 | Continue |
| 5 | 2 | 5 | 5 | Continue |
| 6 | 1 | 6 | 6 | Best subarray here |
| 7 | -5 | 1 | 6 | Slight drop |
| 8 | 4 | 5 | 6 | Continue |
Final Answer = 6
🧩 Approach 3: Divide & Conquer (O(n log n))
This approach is more complex but often asked as a follow-up.
It uses the same idea as merge sort:
Steps:
- Divide the array into two halves
- Conquer recursively for
- Left half
- Right half
- Combine by calculating:
- Maximum subarray that crosses the middle
- Final result =
max(left_result, right_result, crossing_result)
🎯 Why Does This Work?
When we split the array:
There are only 3 possible places where the max subarray can lie:
1️⃣ Entirely in the left half
2️⃣ Entirely in the right half
3️⃣ Crosses the middle (part left, part right)
We compute all three and return the maximum.
🔍 How to Compute the Middle Crossing Subarray
To check crossing subarray:
- Start from middle and go left, collecting the best sum
- Start from middle+1 and go right, collecting the best sum
- Add both together
This gives the largest sum that “crosses” the middle point.
✔ Divide & Conquer Code
def maxCrossingSum(nums, left, mid, right):
# Include elements on left of mid
left_sum = float('-inf')
current = 0
for i in range(mid, left-1, -1):
current += nums[i]
left_sum = max(left_sum, current)
# Include elements on right of mid
right_sum = float('-inf')
current = 0
for i in range(mid+1, right+1):
current += nums[i]
right_sum = max(right_sum, current)
return left_sum + right_sum
def maxSubArrayDivide(nums, left, right):
# Base case: one element
if left == right:
return nums[left]
mid = (left + right) // 2
# Find max in left half, right half, and crossing
left_max = maxSubArrayDivide(nums, left, mid)
right_max = maxSubArrayDivide(nums, mid+1, right)
cross_max = maxCrossingSum(nums, left, mid, right)
return max(left_max, right_max, cross_max)
def maxSubArray_DnC(nums):
return maxSubArrayDivide(nums, 0, len(nums)-1)
🆚 Comparison of All Approaches
| Approach | Time Complexity | Space | Difficulty | Useful For |
|---|---|---|---|---|
| Brute Force | O(n²) | O(1) | Easy | Understanding subarrays |
| Kadane’s | O(n) | O(1) | Medium | Best real-world solution |
| Divide & Conquer | O(n log n) | O(log n) | Hard | Learning recursion patterns |
🏁 Final Summary
The Maximum Subarray problem teaches important lessons:
- How to handle negative values
- How to track continuous running sums
- How dynamic programming decisions are made
- How divide and conquer reduces large problems
The best possible solution is Kadane’s Algorithm, which solves the problem in O(n) time with only constant memory.
Leave a Reply