Problem: Maximum Contiguous Subarray
Let A be an array of numbers. We need to find the largest sum of any contiguous subarray of A.
In an array, a contiguous part is made of elements that appear one after another in order, without skipping.
Example:A = [9, -5, 7, -8, 2]
[9, -5, 7] is contiguous (because the elements are side by side)[9, 7, -8] is not contiguous (because we skipped -5)
A subarray is a slice (or segment) of the array formed by picking a starting index and an ending index, and taking everything between them. Subarrays must be contiguous by definition (unlike subsequences, which may skip elements). A single element is still a contiguous subarray.
We need to return the largest sum of any contiguous subarray of A
Exhaustive Logic (Brute Force):
To find the maximum sum of a contiguous subarray, we need to consider all possible subarrays and keep track of the largest sum encountered. Since we are examining every possible contiguous segment of the array, the question is: how many subarrays can be formed from an array of length n?
For an array of length n, the number of possible contiguous subarrays is n(n+1)/2. Here is why:
- Subarrays starting at index 0: n possibilities (lengths 1 to n)
- Subarrays starting at index 1: n-1 possibilities
- Subarrays starting at index 2: n-2 possibilities
- And so on…
This gives us:
= n + (n-1) + (n-2) + … + 1
= n(n+1)/2Algorithm:
- Generate all subarrays: For each starting position i, consider all possible ending positions j (where j ≥ i)
- Calculate sum: For each subarray from i to j, compute the sum of elements
- Track maximum: Keep a running record of the highest sum found
max_subarray_sum_brute_force(arr):
"""
Find maximum sum of contiguous subarray using brute force approach.
Time Complexity: O(n^3)
Space Complexity: O(1)
"""
n = len(arr)
max_sum = -inf' //Initialize to negative infinity
# Generate all possible subarrays
for (s = 1; s <= n; s++) // Starting position
for (e = s; e <=n; e++) // Ending position (j >= i)
// Calculate sum of current subarray from i to j
current_sum = 0
for (i = s; i <= e; i++) // Get the sum of the subarray
current_sum += arr[i]
// Track maximum sum found so far
if (current_sum > max_sum)
max_sum = current_sum;
return max_sumThe runtime is O(n³)
In this approach, we can notice that we are computing the same sums repeatedly. For example, A = [9, -5, 7, -8, 2, -11, 15, -4]- Subarray [9]: sum = 9
- Subarray [9, -5]: sum = 9 + (-5) = 4 (recalculates 9)
- Subarray [9, -5, 7]: sum = 9 + (-5) + 7 = 11 (recalculates 9 + (-5))
- Subarray [9, -5, 7, -8]: sum = 9 + (-5) + 7 + (-8) = 3 (recalculates 9 + (-5) + 7))
and so on
Instead of recalculating from scratch, we build the sum incrementally as we extend the subarray:
max_subarray_sum_brute_force_optimized(arr):
"""
Find maximum sum of contiguous subarray using brute force approach.
Time Complexity: O(n^2)
Space Complexity: O(1)
"""
n = len(arr)
max_sum = -inf' //Initialize to negative infinity
// Generate all possible subarrays
for (s = 1; s <= n; s++) // Starting position
current_sum = 0 // Reset sum for new starting point
for (e = s; e <=n; e++) // Ending position (e >= e)
current_sum += arr[e] // Add next element incrementally
//Track maximum sum found so far
if (current_sum > max_sum)
max_sum = current_sum;
return max_sumThe third inner loop that recalculated sums from scratch was eliminated. As we extend the ending e position, we simply add arr[e] to the running sum. This gives us the sum of the subarray [i..j] without recalculation.
Now, let’s modify the algorithm to track not just the maximum sum, but also the indices of the subarray that produces this maximum
max_subarray_sum_brute_force_optimized(arr):
"""
Find maximum sum of contiguous subarray using brute force approach.
Time Complexity: O(n^2)
Space Complexity: O(1)
"""
n = len(arr)
max_sum = -inf' //Initialize to negative infinity
best_start_index = 0 //For tracking the best start index
best_end_index = 0 //For tracking the best end index
// Generate all possible subarrays
for (s = 1; s <= n; s++) // Starting position
current_sum = 0 // Reset sum for new starting point
for (e = s; e <=n; e++) // Ending position (e >= e)
current_sum += arr[e] // Add next element incrementally
# Track maximum sum found so far
if (current_sum > max_sum)
max_sum = current_sum;
best_start_index = s
best_end_index = e
return max_sum, best_start_index, best_end_indexRecursive Logic
Think of recursion as a family tree of computations:
- The father holds the last element of the array.
- He asks his son to compute the maximum sum of the subarray that ends before him.
- The son then becomes the father for the next step, holding the second-to-last element and asking his son to compute the subarray sum before him.
- This continues until we reach the first element of the array.
For example, A = [-9, 2, -1, 5, 4, -3, 7]
- Father holds 7 → asks his son to solve [-9 … -3].
- Son holds –3 → asks his son to solve [-9 … 4].
- Son holds 4 → asks his son to solve [-9 … 5].
- … and so on, until we reach the base case (first element –9).
The base case in this problem is when the array has only a single element. In that case, we simply return that element, since it will be the maximum contiguous subarray.
max_subarray_sum_recursive(A, n):
# Base case: single element
if n == 1:
return A[1] # Note: 1-indexed array
else:
# Recursively find max sum in first (n-1) elements
largestSum = max_subarray_sum_recursive(A, n-1)
# Check all subarrays ending at position n
localSum = 0
for i in range(n, 0, -1): # from n down to 1
localSum += A[i]
if localSum > largestSum:
largestSum = localSum
return largestSumThis algorithm works by:
- Recursively finding the maximum sum in the first n-1 elements
- Iteratively checking all subarrays that end at position n. This makes sure we compare all the subarrays that are not compared by the son. Father compares those using the for loop.
- Returning the maximum of these two cases
Caller: the code that invokes a function.
Callee: the function that gets invoked.
def square(x): # callee
return x * xy = square(5) # caller
The parameters — array A and its length n—carry information from the caller to the callee (from one generation to the next). The return value carries information back from the callee to the caller.
Example for the array: A = [-9, 2, -1, 5, 4, -3, 7]
We are using a starting index of 1.
max_subarray_sum_recursive(A, 7)
├── max_subarray_sum_recursive(A, 6)
│ ├── max_subarray_sum_recursive(A, 5)
│ │ ├── max_subarray_sum_recursive(A, 4)
│ │ │ ├── max_subarray_sum_recursive(A, 3)
│ │ │ │ ├── max_subarray_sum_recursive(A, 2)
│ │ │ │ │ ├── max_subarray_sum_recursive(A, 1) → BASE CASE: RETURNS -9
│ │ │ │ │ └── ELSE: largestSum=-9, check subarrays ending at pos 2, n = 2
│ │ │ │ │ ├── i=2: localSum = 0 + A[2] = 0 + 2 = 2, largestSum = max(-9,2) = 2
│ │ │ │ │ └── i=1: localSum = 2 + A[1] = 2 + -9 = -7, largestSum = max(2,-7) = 2
│ │ │ │ │ RETURNS: 2
│ │ │ │ └── ELSE: largestSum=2, check subarrays ending at pos 3
│ │ │ │ ├── i=3: localSum = 0 + A[3] = 0 + (-1) = -1, largestSum = max(2,-1) = 2
│ │ │ │ ├── i=2: localSum = -1 + A[2] = (-1) + 2 = 1, largestSum = max(2,1) = 2
│ │ │ │ └── i=1: localSum = 1 + A[1] = 1 + (-9) = -8, largestSum = max(2,-8) = 2
│ │ │ │ RETURNS: 2
│ │ │ └── ELSE: largestSum=2, check subarrays ending at pos 4
│ │ │ ├── i=4: localSum = 0 + A[4] = 5, largestSum = max(2,5) = 5
│ │ │ ├── i=3: localSum = 5 + A[3] = 4, largestSum = max(5,4) = 5
│ │ │ ├── i=2: localSum = 4 + A[2] = 6, largestSum = max(5,6) = 6
│ │ │ └── i=1: localSum = 6 + A[1] = -3, largestSum = max(6,-3) = 6
│ │ │ RETURNS: 6
│ │ └── ELSE: largestSum=6, check subarrays ending at pos 5
│ │ ├── i=5: localSum = 0 + A[5] = 4, largestSum = max(6,4) = 6
│ │ ├── i=4: localSum = 4 + A[4] = 9, largestSum = max(6,9) = 9
│ │ ├── i=3: localSum = 9 + A[3] = 8, largestSum = max(9,8) = 9
│ │ ├── i=2: localSum = 8 + A[2] = 10, largestSum = max(9,10) = 10
│ │ └── i=1: localSum = 10 + A[1] = 1, largestSum = max(10,1) = 10
│ │ RETURNS: 10
│ └── ELSE: largestSum=10, check subarrays ending at pos 6
│ ├── i=6: localSum = 0 + A[6] = -3, largestSum = max(10,-3) = 10
│ ├── i=5: localSum = -3 + A[5] = 1, largestSum = max(10,1) = 10
│ ├── i=4: localSum = 1 + A[4] = 6, largestSum = max(10,6) = 10
│ ├── i=3: localSum = 6 + A[3] = 5, largestSum = max(10,5) = 10
│ ├── i=2: localSum = 5 + A[2] = 7, largestSum = max(10,7) = 10
│ └── i=1: localSum = 7 + A[1] = -2, largestSum = max(10,-2) = 10
│ RETURNS: 10
└── ELSE: largestSum=10, check subarrays ending at pos 7
├── i=7: localSum = 0 + A[7] = 7, largestSum = max(10,7) = 10
├── i=6: localSum = 7 + A[6] = 4, largestSum = max(10,4) = 10
├── i=5: localSum = 4 + A[5] = 8, largestSum = max(10,8) = 10
├── i=4: localSum = 8 + A[4] = 13, largestSum = max(10,13) = 13
├── i=3: localSum = 13 + A[3] = 12, largestSum = max(13,12) = 13
├── i=2: localSum = 12 + A[2] = 14, largestSum = max(13,14) = 14
└── i=1: localSum = 14 + A[1] = 5, largestSum = max(14,5) = 14
RETURNS: 14You can visualize this approach using Python Tutor by pasting the code below into the editor.
def max_subarray_sum_recursive(A, n):
"""
Maximum Contiguous Subarray Sum - Recursive Algorithm
Args:
A: 0-indexed array
n: length of the array to consider (number of elements)
Returns:
Maximum sum of contiguous subarray
"""
# Base case: single element
if n == 1:
return A[0] # 0-indexed: first element is A[0]
else:
# Recursively find max sum in first (n-1) elements
largestSum = max_subarray_sum_recursive(A, n-1)
# Check all subarrays ending at position n-1 (0-indexed)
localSum = 0
for i in range(n-1, -1, -1): # from (n-1) down to 0
localSum += A[i]
if localSum > largestSum:
largestSum = localSum
return largestSum
max_subarray_sum_recursive([-9, 2, -1, 5, 4, -3, 7], 7)
In this approach, the ending index was always fixed. That is, we always end at the current position and vary the starting positions. For example, A = [-9, 2, -1, 5, 4, -3, 7]:
- Father holds value 7, i.e, the ending index→ asks his son to solve the problem ending at position 5: [-9, 2, -1, 5, 4, -3].
- Son holds value -3, i.e, the ending index of that subarray→ asks his son to solve the problem ending at position 4: [-9, 2, -1, 5, 4].
- Son at ending position 4 (value 4) → asks his son to solve the problem ending at position 3: [-9, 2, -1, 5].
- And so on…
Each father also computes the best subarray sum ending at his position by checking all possible starting positions that lead to his ending position, then returns the maximum of his result and his son’s result.
Now, we want to solve this same problem by making the start move forward. For example, A = [-9, 2, -1, 5, 4, -3, 7]:
- Father at position 0 (holds -9) → asks his son to solve [2, -1, 5, 4, -3, 7] starting from position 1.
- Son at position 1 (holds 2) → asks his son to solve [-1, 5, 4, -3, 7] starting from position 2.
- Son at position 2 (holds -1) → asks his son to solve [5, 4, -3, 7] starting from position 3.
- And so on…
Each father also computes the best subarray sum starting from his position (scanning forward to the end), then returns the maximum of his result and his son’s result.
max_subarray_sum_recursive_hold_first_element(A, low, high):
// low = start index of the array A
// high = last index of the array A
if (low == high):
return A[low]
else: // low < high
largestSum = max_subarray_sum_recursive_hold_first_element(A, low + 1, high)
localSum = 0
for (i = low; i <= high; i++)
localSum += A[i]
if localSum > largestSum:
largestSum = localSum
return largestSumThe initial call will be max_subarray_sum_recursive_hold_first_element(A, 1, A.length)
Get Prajun Trital’s stories in your inbox
Join Medium for free to get updates from this writer.
Example for the array: A = [-9, 2, -1, 5, 4, -3, 7]
We are using a starting index of 1.
max_subarray_sum_recursive_hold_first_element(A, 1, 7)
├── max_subarray_sum_recursive_hold_first_element(A, 2, 7)
│ ├── max_subarray_sum_recursive_hold_first_element(A, 3, 7)
│ │ ├── max_subarray_sum_recursive_hold_first_element(A, 4, 7)
│ │ │ ├── max_subarray_sum_recursive_hold_first_element(A, 5, 7)
│ │ │ │ ├── max_subarray_sum_recursive_hold_first_element(A, 6, 7)
│ │ │ │ │ ├── max_subarray_sum_recursive_hold_first_element(A, 7, 7) → BASE CASE: RETURNS A[7] = 7
│ │ │ │ │ └── ELSE: largestSum=7, check subarrays starting at pos 6
│ │ │ │ │ ├── i=6: localSum = 0 + A[6] = 0 + (-3) = -3, largestSum = max(7,-3) = 7
│ │ │ │ │ └── i=7: localSum = -3 + A[7] = -3 + 7 = 4, largestSum = max(7,4) = 7
│ │ │ │ │ RETURNS: 7
│ │ │ │ └── ELSE: largestSum=7, check subarrays starting at pos 5
│ │ │ │ ├── i=5: localSum = 0 + A[5] = 0 + 4 = 4, largestSum = max(7,4) = 7
│ │ │ │ ├── i=6: localSum = 4 + A[6] = 4 + (-3) = 1, largestSum = max(7,1) = 7
│ │ │ │ └── i=7: localSum = 1 + A[7] = 1 + 7 = 8, largestSum = max(7,8) = 8
│ │ │ │ RETURNS: 8
│ │ │ └── ELSE: largestSum=8, check subarrays starting at pos 4
│ │ │ ├── i=4: localSum = 0 + A[4] = 0 + 5 = 5, largestSum = max(8,5) = 8
│ │ │ ├── i=5: localSum = 5 + A[5] = 5 + 4 = 9, largestSum = max(8,9) = 9
│ │ │ ├── i=6: localSum = 9 + A[6] = 9 + (-3) = 6, largestSum = max(9,6) = 9
│ │ │ └── i=7: localSum = 6 + A[7] = 6 + 7 = 13, largestSum = max(9,13) = 13
│ │ │ RETURNS: 13
│ │ └── ELSE: largestSum=13, check subarrays starting at pos 3
│ │ ├── i=3: localSum = 0 + A[3] = 0 + (-1) = -1, largestSum = max(13,-1) = 13
│ │ ├── i=4: localSum = -1 + A[4] = -1 + 5 = 4, largestSum = max(13,4) = 13
│ │ ├── i=5: localSum = 4 + A[5] = 4 + 4 = 8, largestSum = max(13,8) = 13
│ │ ├── i=6: localSum = 8 + A[6] = 8 + (-3) = 5, largestSum = max(13,5) = 13
│ │ └── i=7: localSum = 5 + A[7] = 5 + 7 = 12, largestSum = max(13,12) = 13
│ │ RETURNS: 13
│ └── ELSE: largestSum=13, check subarrays starting at pos 2
│ ├── i=2: localSum = 0 + A[2] = 0 + 2 = 2, largestSum = max(13,2) = 13
│ ├── i=3: localSum = 2 + A[3] = 2 + (-1) = 1, largestSum = max(13,1) = 13
│ ├── i=4: localSum = 1 + A[4] = 1 + 5 = 6, largestSum = max(13,6) = 13
│ ├── i=5: localSum = 6 + A[5] = 6 + 4 = 10, largestSum = max(13,10) = 13
│ ├── i=6: localSum = 10 + A[6] = 10 + (-3) = 7, largestSum = max(13,7) = 13
│ └── i=7: localSum = 7 + A[7] = 7 + 7 = 14, largestSum = max(13,14) = 14
│ RETURNS: 14
└── ELSE: largestSum=14, check subarrays starting at pos 1
├── i=1: localSum = 0 + A[1] = 0 + (-9) = -9, largestSum = max(14,-9) = 14
├── i=2: localSum = -9 + A[2] = -9 + 2 = -7, largestSum = max(14,-7) = 14
├── i=3: localSum = -7 + A[3] = -7 + (-1) = -8, largestSum = max(14,-8) = 14
├── i=4: localSum = -8 + A[4] = -8 + 5 = -3, largestSum = max(14,-3) = 14
├── i=5: localSum = -3 + A[5] = -3 + 4 = 1, largestSum = max(14,1) = 14
├── i=6: localSum = 1 + A[6] = 1 + (-3) = -2, largestSum = max(14,-2) = 14
└── i=7: localSum = -2 + A[7] = -2 + 7 = 5, largestSum = max(14,5) = 14
RETURNS: 14We can achieve this by just passing two parameters, that is Array(A) and low index.
max_subarray_sum_recursive_hold_first_element(A, low):
// low = start index of the array A
n = length(A) // array length
if (low == n):
return A[low]
else: // low < high
largestSum = max_subarray_sum_recursive_hold_first_element(A, low + 1)
localSum = 0
for (i = low; i <= n; i++)
localSum += A[i]
if localSum > largestSum:
largestSum = localSum
return largestSumInitial call max_subarray_sum_recursive_hold_first_element(A, 1)
We are using 1-based indices.
Here, this solution also has a time complexity of O(n^2) and the recursion depth is O(n) .
Recursion depth O(n) means the algorithm’s call stack grows linearly with the input size n. In other words, the maximum number of active function calls at once is proportional to n. Each call reduces the problem size by 1 (e.g., from
lowtolow+1or fromnton-1and so on)
Optimal Solution: Kadane’s Algorithm
Imagine you’re walking through the array from left to right, and at each step you ask yourself: “Should I keep adding to my current sum, or should I throw it away and start fresh from here?”
Array: [5, -3, 4, -1, 2, -5, 8]Start with 5:
- Current running sum: 5
- Best I've ever seen: 5
See -3:
- "Should I do (5 + (-3) = 2) or start fresh with -3?"
- Keep going with 2 (better than -3)
- Current running sum: 2
- Best I've ever seen: still 5 (2 isn't better)
See 4:
- "Should I do (2 + 4 = 6) or start fresh with 4?"
- Keep going with 6 (better than 4)
- Current running sum: 6
- Best I've ever seen: now 6! (better than my old record of 5)
See -1:
- "Should I do (6 + (-1) = 5) or start fresh with -1?"
- Keep going with 5 (way better than -1)
- Current running sum: 5
- Best I've ever seen: still 6 (my current 5 isn't beating my record)
See 2:
- "Should I do (5 + 2 = 7) or start fresh with 2?"
- Keep going with 7
- Current running sum: 7
- Best I've ever seen: now 7! (new record!)
See -5:
- "Should I do (7 + (-5) = 2) or start fresh with -5?"
- Keep going with 2 (better than -5)
- Current running sum: 2 (ouch, dropped a lot!)
- Best I've ever seen: still 7 (good thing I remembered my peak!)
See 8:
- "Should I do (2 + 8 = 10) or start fresh with 8?"
- Keep going with 10
- Current running sum: 10
- Best I've ever seen: now 10! (new champion!)
Final answer: 10
The Rule:
- If extending the current sum is better than starting fresh: Keep extending!
- If starting fresh is better than extending: Start over!
At each element, ask: “Is (my_running_sum + new_element) better than just (new_element) alone?”
Any subarray that gives a worse running total than just starting fresh is hurting. So whenever extending the current sum makes things worse than restarting, we “reset” and start fresh.
That’s it! Kadane’s algorithm is just this greedy decision: “Always pick whichever gives you the bigger sum — extending or restarting.”
Using 0-based index
max_subarray_kadane(A):
// Using 0-based index
max_sum_global = A[0] // best sum seen anywhere so far
max_sum_ending_here = A[0] // best sum of subarray ending at i
for (i = 1; i <= A.length - 1; i++)
// extend previous run or restart at A[i]
if (max_sum_ending_here + A[i] >= A[i])
max_sum_ending_here = max_sum_ending_here + A[i]
else
max_sum_ending_here = A[i]
// update global best if needed
if (max_sum_ending_here > max_sum_global)
max_sum_global = max_sum_ending_here
return max_sum_globalThe time complexity is O(n)
Here is the python version of the code that we can try in Python Tutor for visualization.
def max_subarray_kadane(A):
max_sum_global = A[0] # best sum seen anywhere so far
max_sum_ending_here = A[0] # best sum of subarray ending at i
for i in range(1, len(A)):
# extend previous run or restart at A[i]
if max_sum_ending_here + A[i] >= A[i]:
max_sum_ending_here = max_sum_ending_here + A[i]
else:
max_sum_ending_here = A[i]
# update global best if needed
if max_sum_ending_here > max_sum_global:
max_sum_global = max_sum_ending_here
return max_sum_global
# Test cases
A = [-9, 2, -1, 5, 4, -3, 7]
result = max_subarray_kadane(A)
print(f"Array: {A}")
print(f"Maximum subarray sum: {result}")
A2 = [5, -3, 4, -1, 2, -5, 8]
result2 = max_subarray_kadane(A2)
print(f"\nArray: {A2}")
print(f"Maximum subarray sum: {result2}")
A3 = [-5, -2, -8, -1]
result3 = max_subarray_kadane(A3)
print(f"\nArray: {A3}")
print(f"Maximum subarray sum: {result3}")Some Leetcode problems to practice (Most asked in interviews):
- 53. Maximum Subarray — the classic Kadane starter. LeetCode
- 121. Best Time to Buy and Sell Stock — transform to Kadane on day-to-day diffs (single transaction). LeetCode
- 152. Maximum Product Subarray — Kadane-like, but track max/min because of negatives. LeetCode
- 560. Subarray Sum Equals K — counts subarrays with sum K (prefix-sum + hashmap; not Kadane but essential). LeetCode
This one is common but less frequent in interviews
- 918. Maximum Sum Circular Subarray — Kadane + wrap-around trick (max(non-wrap), total − min-subarray). LeetCode
Additional ones
- 1186. Maximum Subarray Sum with One Deletion — allow dropping one element; DP/Kadane variant. LeetCode
- 1749. Maximum Absolute Sum of Any Subarray — need both max and min Kadane to maximize |sum|. LeetCode
- 1191. K-Concatenation Maximum Sum — Kadane across repeated arrays; uses prefix/suffix/total-sum logic. LeetCode
