Maximum Subarray and Maximum Product Subarray
Apply Kadane's algorithm to maximum-sum-subarray and extend it to track both maximum and minimum for the product variant.
Maximum Subarray and Maximum Product Subarray is a free DSA Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Maximum Sum Subarray Problem
The Maximum Subarray problem asks you to find the contiguous subarray within a one-dimensional array of numbers that has the largest sum. For example, in [-2, 1, -3, 4, -1, 2, 1, -5, 4], the subarray [4, -1, 2, 1] gives the maximum sum of 6. A brute-force O(n²) approach checks all subarrays, but Kadane's algorithm solves it in O(n).
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
# Brute force: O(n^2)
max_sum = float('-inf')
for i in range(len(nums)):
curr = 0
for j in range(i, len(nums)):
curr += nums[j]
max_sum = max(max_sum, curr)
print(max_sum) # 6Kadane's Algorithm Intuition
Kadane's algorithm makes one pass through the array, maintaining a running current_sum. At each element, you decide: is it better to extend the existing subarray or start fresh from this element? If current_sum becomes negative, it would only hurt any future subarray, so restart. The recurrence is current_sum = max(num, current_sum + num).
def max_subarray(nums):
max_sum = current_sum = nums[0]
for num in nums[1:]:
# Extend or start fresh?
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray(nums)) # 6Tracing Kadane's Algorithm
Let's trace Kadane's on [-2, 1, -3, 4, -1, 2, 1, -5, 4]: start with curr=-2, max=-2. At 1: curr=max(1,-2+1)=1, max=1. At -3: curr=max(-3,1-3)=-2, max=1. At 4: curr=max(4,-2+4)=4, max=4. At -1: curr=3, max=4. At 2: curr=5, max=5. At 1: curr=6, max=6. At -5: curr=1. At 4: curr=5, max=6. The algorithm correctly identifies the subarray ending at index 6 as optimal.
def max_subarray_trace(nums):
curr = max_sum = nums[0]
for i, num in enumerate(nums[1:], 1):
new_curr = max(num, curr + num)
max_sum = max(max_sum, new_curr)
print(f'i={i}, num={num}, curr: {curr}->{new_curr}, max={max_sum}')
curr = new_curr
return max_sum
max_subarray_trace([-2, 1, -3, 4, -1, 2, 1, -5, 4])Returning the Actual Subarray
If the interviewer asks you to return the subarray itself (not just the sum), you need to track start and end indices. When you restart (because num > current_sum + num), update a temp_start. When you update max_sum, save temp_start as start and the current index as end. This adds O(1) overhead to the same O(n) algorithm.
def max_subarray_indices(nums):
max_sum = curr = nums[0]
start = end = temp_start = 0
for i in range(1, len(nums)):
if nums[i] > curr + nums[i]:
curr = nums[i]
temp_start = i
else:
curr += nums[i]
if curr > max_sum:
max_sum = curr
start, end = temp_start, i
return max_sum, nums[start:end+1]
print(max_subarray_indices([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
# (6, [4, -1, 2, 1])Maximum Product Subarray Problem
The Maximum Product Subarray problem is trickier than the sum variant because of negative numbers. Two negatives multiply to a positive, so a very negative product can become the maximum after multiplying by another negative. For [2, 3, -2, 4], the answer is 6 ([2, 3]). For [-2, 0, -1], the answer is 0. We must track both maximum and minimum products at each step.
nums = [2, 3, -2, 4]
# [2,3,-2,4]: products [2, 6, -12, -48]
# subarrays: [2]=2, [2,3]=6, [3]=3, etc.
# max is 6 from subarray [2,3]
nums2 = [-2, 3, -4]
# [-2]*3*[-4] = 24
# negative*negative=positive!
print('Expected:', 24)Tracking Both Max and Min Products
The key insight: at each position, the current maximum product is one of num, max_so_far * num, or min_so_far * num (the last one helps when a negative flips the minimum to maximum). Similarly for the minimum. Update both cur_max and cur_min simultaneously using the previous values to avoid using already-updated values in the same step.
def max_product(nums):
max_prod = min_prod = result = nums[0]
for num in nums[1:]:
# All three candidates for new max
candidates = (num, max_prod * num, min_prod * num)
max_prod, min_prod = max(candidates), min(candidates)
result = max(result, max_prod)
return result
print(max_product([2, 3, -2, 4])) # 6
print(max_product([-2, 3, -4])) # 24
print(max_product([-2, 0, -1])) # 0
print(max_product([-2])) # -2Why min_prod Matters
Consider [-3, -10, 5]. After processing -3: max=-3, min=-3. After -10: candidates are (-10, 30, 30) → max=30, min=-10. After 5: candidates are (5, 150, -50) → max=150. Without tracking min_prod, you would miss the flip that occurs when a large-negative minimum is multiplied by another negative. Always compute both max and min from the same previous values to avoid a stale-read bug.
def max_product_traced(nums):
max_p = min_p = result = nums[0]
for num in nums[1:]:
prev_max, prev_min = max_p, min_p
max_p = max(num, prev_max * num, prev_min * num)
min_p = min(num, prev_max * num, prev_min * num)
result = max(result, max_p)
print(f'num={num}: max_p={max_p}, min_p={min_p}')
return result
max_product_traced([-3, -10, 5])
# max_p after -10: 30 (flip!)
# max_p after 5: 150Zeros Reset the Product
A zero in the array resets both running products to zero, effectively splitting the array into independent subarrays. When num = 0, both max_prod * 0 = 0 and min_prod * 0 = 0, so all three candidates become 0, and the maximum of the previous result is preserved. No special-case code is needed — the general formula handles zeros naturally.
def max_product(nums):
max_p = min_p = result = nums[0]
for num in nums[1:]:
cands = (num, max_p * num, min_p * num)
max_p, min_p = max(cands), min(cands)
result = max(result, max_p)
return result
# Zero splits array into independent subarrays
print(max_product([3, -1, 4, 0, 2, 5, -1])) # 10 (2*5)
print(max_product([0, 2])) # 2
print(max_product([-1, 0, -2])) # 0Alternative: Left-Right Product Sweep
An alternative approach sweeps left to right and right to left, resetting the running product to 1 when it hits zero. The maximum product subarray never crosses a zero, so if a negative number makes things bad in one direction, the reverse sweep will catch the flip. This approach is elegant but the min/max tracking method is more commonly expected in interviews.
def max_product_sweep(nums):
result = max(nums)
left = right = 1
n = len(nums)
for i in range(n):
left *= nums[i]
right *= nums[n - 1 - i]
result = max(result, left, right)
if left == 0: left = 1
if right == 0: right = 1
return result
print(max_product_sweep([2, 3, -2, 4])) # 6
print(max_product_sweep([-2, 3, -4])) # 24
print(max_product_sweep([-2, 0, -1])) # 0Kadane's vs Product: Key Differences
Sum and product subarrays differ in important ways. For sum: negatives are always harmful, so you restart greedily. For product: two negatives help, so you must track both extremes. Additionally, zeros are terminal for products but only mildly harmful for sums. When communicating in interviews, explicitly acknowledge these differences and explain why tracking min is necessary before writing any code.
# Max Sum Subarray: O(n) time, O(1) space
def max_sum(nums):
curr = result = nums[0]
for n in nums[1:]:
curr = max(n, curr + n) # restart or extend
result = max(result, curr)
return result
# Max Product Subarray: O(n) time, O(1) space
def max_prod(nums):
lo = hi = result = nums[0]
for n in nums[1:]:
lo, hi = min(n, lo*n, hi*n), max(n, lo*n, hi*n)
result = max(result, hi)
return result
print(max_sum([-2, 1, -3, 4, -1, 2, 1])) # 6
print(max_prod([-2, 3, -4])) # 24Complexity and Interview Tips
Both Kadane's algorithm (max sum) and the min/max tracking (max product) run in O(n) time and O(1) space. Key interview tips: (1) For max sum, mention the Divide and Conquer O(n log n) alternative to show breadth. (2) For max product, emphasise that you update min_prod and max_prod simultaneously from previous values to avoid using stale data. (3) Always clarify: can the array be empty? Must the subarray be non-empty? (Yes, it must be non-empty by convention.)
# Both run O(n) time, O(1) space
# Kadane handles: all negative (returns least negative)
# Product handles: zeros (resets naturally), negatives (tracks both extremes)
nums_all_neg = [-5, -2, -8]
print('Max sum (all neg):', max(max(nums_all_neg[0:1]),
max(x for x in nums_all_neg))) # -2
# Correct: return the maximum element when all are negativeQuick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: Kadane's algorithm solves maximum sum subarray in O(n) by choosing to extend or restart at each element, maximum product subarray requires tracking both minimum and maximum running products due to negative number flips, and zeros naturally reset the running product without special-case code. Next up we explore the Word Break problem using a 1D DP table.
Frequently asked questions
Is the “Maximum Subarray and Maximum Product Subarray” lesson free?
Yes — the full text of “Maximum Subarray and Maximum Product Subarray” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Maximum Subarray and Maximum Product Subarray”?
Apply Kadane's algorithm to maximum-sum-subarray and extend it to track both maximum and minimum for the product variant. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Maximum Subarray and Maximum Product Subarray” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- House Robber: Take-or-Skip Recurrence
- Maximum Subarray and Maximum Product Subarray
- Word Break and Segment String
- Decode Ways and Counting Paths