⚡ TL;DR
Solve Maximum Subarray in Python four ways — Kadane's O(n) algorithm, brute force, divide-and-conquer, and index tracking — with interview tips.
Maximum Subarray (#53 — Medium): Given an integer array nums, find the contiguous subarray with the largest sum and return its sum. Kadane’s algorithm solves it in O(n) time — a classic dynamic programming interview question every Python developer should know.
Problem Statement
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Examples:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the sum 6.
Input: nums = [1]
Output: 1
Input: nums = [5,4,-1,7,8]
Output: 23Approach: Kadane’s Algorithm (Optimal)
Time: O(n) | Space: O(1)
Track the best sum ending at each index. For position i, the best sum ending there is either:
nums[i](start a new subarray), ORnums[i] + best_sum_at_i-1(extend the previous subarray)
def max_subarray_kadane(nums):
if not nums:
return 0
max_so_far = nums[0] # global max
max_ending_here = nums[0] # best sum ending at current position
for num in nums[1:]:
# Either start a new subarray OR extend the existing one
max_ending_here = max(num, max_ending_here + num)
# Update the global max
max_so_far = max(max_so_far, max_ending_here)
return max_so_far
# Test
print(max_subarray_kadane([-2,1,-3,4,-1,2,1,-5,4])) # 6
print(max_subarray_kadane([5,4,-1,7,8])) # 23
print(max_subarray_kadane([-1])) # -1This is the interview-standard answer.
Walkthrough of Kadane’s Algorithm
For nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]:
| Index | Value | max_ending_here | max_so_far | Decision |
|---|---|---|---|---|
| 0 | -2 | -2 | -2 | start new |
| 1 | 1 | 1 | 1 | new is better than -2+1 |
| 2 | -3 | -2 | 1 | extend: 1 + (-3) = -2 |
| 3 | 4 | 4 | 4 | new: -2+4=2, better to start at 4 |
| 4 | -1 | 3 | 4 | extend: 4 - 1 = 3 |
| 5 | 2 | 5 | 5 | extend: 3 + 2 = 5 |
| 6 | 1 | 6 | 6 | extend: 5 + 1 = 6 (best so far) |
| 7 | -5 | 1 | 6 | extend: 6 - 5 = 1 |
| 8 | 4 | 5 | 6 | extend: 1 + 4 = 5 |
Final answer: 6 (from subarray [4, -1, 2, 1])
Approach: Brute Force
Time: O(n²) | Space: O(1)
Generate every possible subarray and track the maximum sum. Too slow for interviews, but useful to validate correctness on small inputs.
def max_subarray_brute(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]
if current_sum > max_sum:
max_sum = current_sum
return max_sum
# Test
print(max_subarray_brute([-2,1,-3,4,-1,2,1,-5,4])) # 6Approach: Divide & Conquer
Time: O(n log n) | Space: O(log n)
Split the array in half. The answer is either:
- Entirely in the left half
- Entirely in the right half
- Crossing the middle (left suffix + right prefix)
def max_subarray_dc(nums):
def max_crossing_sum(arr, left, mid, right):
# Left part: from mid to left
left_sum = float('-inf')
current_sum = 0
for i in range(mid, left - 1, -1):
current_sum += arr[i]
if current_sum > left_sum:
left_sum = current_sum
# Right part: from mid+1 to right
right_sum = float('-inf')
current_sum = 0
for i in range(mid + 1, right + 1):
current_sum += arr[i]
if current_sum > right_sum:
right_sum = current_sum
return left_sum + right_sum
def max_subarray_recursive(arr, left, right):
if left == right:
return arr[left]
mid = (left + right) // 2
left_max = max_subarray_recursive(arr, left, mid)
right_max = max_subarray_recursive(arr, mid + 1, right)
cross_max = max_crossing_sum(arr, left, mid, right)
return max(left_max, right_max, cross_max)
if not nums:
return 0
return max_subarray_recursive(nums, 0, len(nums) - 1)Good to know if asked, but usually overkill since Kadane’s is simpler.
Approach: Kadane’s with Index Tracking
Time: O(n) | Space: O(1)
Return the subarray indices along with the sum — a common interview follow-up:
def max_subarray_with_indices(nums):
if not nums:
return 0, -1, -1
max_sum = nums[0]
current_sum = nums[0]
start = 0
end = 0
current_start = 0
for i in range(1, len(nums)):
if current_sum + nums[i] < nums[i]:
current_sum = nums[i]
current_start = i
else:
current_sum += nums[i]
if current_sum > max_sum:
max_sum = current_sum
start = current_start
end = i
return max_sum, start, end
# Test
nums = [-2,1,-3,4,-1,2,1,-5,4]
result, start, end = max_subarray_with_indices(nums)
print(f"Max sum: {result}") # 6
print(f"Indices: {start} to {end}") # 3 to 6
print(f"Subarray: {nums[start:end+1]}") # [4, -1, 2, 1]Complexity Comparison
| Approach | Time | Space | Interview Use |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Rarely |
| Kadane’s Algorithm | O(n) | O(1) | ✅ Always use |
| Divide & Conquer | O(n log n) | O(log n) | ✅ If asked |
| Index Tracking | O(n) | O(1) | ⭐ For follow-ups |
Common Mistakes to Avoid
- Initializing with 0 instead of nums[0] — breaks when all numbers are negative
- Forgetting
-inf— using-999doesn’t work for edge cases - Misunderstanding “contiguous” — the subarray must have consecutive elements
- Trying to return indices with original Kadane — leads to off-by-one errors
Practice Exercises
- Modify Kadane to handle all-negative arrays correctly
- Write the max-product variant (take the max of current, previous_max * num, previous_min * num)
- Write a version that returns the actual subarray as a slice
- Implement the circular-array version where the array connects to itself
Key Takeaways
- Start with the brute-force approach to understand the problem
- Kadane’s Algorithm gives the optimal O(n) solution with O(1) space
- The core idea — best sum ending here is
max(num, best + num)— is a reusable dynamic programming pattern that appears frequently in coding interviews
Related Problems
- Maximum Subarray in Dart
- Maximum Subarray in Go
- Maximum Subarray in Swift
- Two Sum in Python
- Remove Duplicates from Sorted Array in Python
- Contains Duplicate in Python
FAQ
What is the best approach to solve Maximum Subarray in Python?
The recommended approach is Kadane’s Algorithm (Optimal), which runs in O(n) time with O(1) space. The full Python implementation is shown above.
What is the time complexity of Maximum Subarray in Python?
Using Kadane’s Algorithm (Optimal), the time complexity is O(n) and the space complexity is O(1).
Happy coding!
