Maximum Subarray
First-principles DP: from "what should I do at each step?" to Kadane

šŸ“‹ Problem Statement

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] Output: 6 Explanation: The subarray [4, -1, 2, 1] has the largest sum 6.

Example 2

Input: nums = [1] Output: 1 Explanation: The subarray [1] has the largest sum 1.

Example 3

Input: nums = [5, 4, -1, 7, 8] Output: 23 Explanation: The subarray [5, 4, -1, 7, 8] has the largest sum 23.

Constraints

We're going to derive the recurrence from scratch ā€” not just memorize Kadane's algorithm. By the end, you'll know why the recurrence takes this shape and how to recognize the same pattern in other problems.

1. What is a subarray? What are we really optimizing?

A subarray is a contiguous segment of the array. Unlike a subsequence, you cannot skip elements.

We want the subarray with the maximum sum. Let's think about what that means one element at a time:

First-principles question

Imagine you're scanning left to right. When you reach position i, you look at nums[i] and ask:

"Should I extend the best subarray ending before me,
or should I start fresh right here?"

This is the only choice at each position ā€” and it's what makes DP work.

Let's make this concrete with [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

At index 0: only one option ā€” take -2. Best subarray ending at 0 has sum -2.

At index 1 (value 1): extend with -2 ā†’ sum -1, or start fresh ā†’ sum 1. Start fresh wins.

At index 3 (value 4): extend the best ending at 2 (-2) ā†’ sum 2, or start fresh ā†’ sum 4. Start fresh wins.

At index 4 (value -1): extend 4 ā†’ sum 3, or start fresh ā†’ sum -1. Extend wins.

The "aha" moment

When is it always better to start fresh? When the previous best is negative ā€” adding a negative to the current number can only make it smaller. When the previous best is positive, extending always improves the sum.

This gives us a simple rule:
if previous_sum > 0 ā†’ extend it. Otherwise ā†’ start fresh.

2. The recurrence relation

Define dp[i] = maximum sum of a subarray ending at index i.

Base case: dp[0] = nums[0] // the only subarray ending at index 0 Recurrence (i ā‰„ 1): dp[i] = max( nums[i], dp[i-1] + nums[i] ) ā””ā”€ start fresh ā”€ā”˜ ā””ā”€ā”€ extend previous ā”€ā”€ā”˜ Final answer: result = max( dp[0], dp[1], ..., dp[n-1] )

Break this down:

Why this recurrence has optimal substructure

To find the best subarray ending at i, we only need:

  1. nums[i] ā€” the current element (given)
  2. dp[i-1] ā€” the best subarray ending at the previous position (already computed)

We don't need to know which subarray produced dp[i-1] ā€” the sum alone is enough. This is the hallmark of 1D DP: each state depends only on the immediately previous state.

The key DP insight: we don't try every possible subarray (that would be O(nĀ²)). Instead, we reuse the answer for subarrays ending at i-1 to compute the answer for subarrays ending at i in O(1). The answer for the whole array is just the maximum over all dp[i].

3. Interactive DP walkthrough

Choose an example array and step through the DP computation:

0 Click "Step Forward" to begin
0.8s

4. The traversal order (why it's simple)

Unlike interval DP (palindromic substring), this is a 1D DP. The traversal is straightforward:

Left-to-right, single pass

dp[i] depends only on dp[i-1]. There's no dependency on future indices or shorter intervals. You can fill the array in a single left-to-right pass ā€” O(n) time.

// Traversal: one pass, left to right for (let i = 1; i < n; i++) { dp[i] = Math.max(nums[i], dp[i-1] + nums[i]); // dp[i-1] is already computed ā†’ safe }
Because each dp[i] depends only on dp[i-1], we can drop the array entirely and keep a single variable. This is Kadane's algorithm ā€” same recurrence, O(1) space.

5. The complete solutions

5a. Full DP array ā€” O(n) time, O(n) space

/** * Maximum Subarray ā€” DP array * dp[i] = max sum of subarray ending at i * Recurrence: dp[i] = max(nums[i], dp[i-1] + nums[i]) */ function maxSubArray(nums) { const n = nums.length; const dp = new Array(n); dp[0] = nums[0]; // Base case let maxSum = dp[0]; for (let i = 1; i < n; i++) { dp[i] = Math.max(nums[i], dp[i-1] + nums[i]); maxSum = Math.max(maxSum, dp[i]); } return maxSum; }

5b. Kadane's Algorithm ā€” O(n) time, O(1) space

/** * Maximum Subarray ā€” Kadane's Algorithm * Space-optimized: track only current dp value */ function maxSubArray(nums) { let currentMax = nums[0]; // dp[i] ā€” best ending at current position let globalMax = nums[0]; // max(dp[0]..dp[i]) for (let i = 1; i < nums.length; i++) { currentMax = Math.max(nums[i], currentMax + nums[i]); globalMax = Math.max(globalMax, currentMax); } return globalMax; }

DP Array Version

  • Explicit dp[i] semantics
  • Easier to reason about
  • Extensible (e.g., reconstruct the subarray)
  • O(n) space

Kadane's Version

  • Same recurrence, different bookkeeping
  • currentMax = dp[i] at step i
  • O(1) space ā€” optimal
  • Standard interview answer

6. Divide and Conquer (the follow-up)

The problem's follow-up asks for a divide and conquer solution. Here's the intuition:

The cross-midpoint insight

For any subarray, one of three things is true:

  1. It lies entirely in the left half
  2. It lies entirely in the right half
  3. It crosses the midpoint (starts in left, ends in right)

Cases 1 and 2 are recursive. Case 3 can be computed in O(n) by finding the max suffix sum of the left half and max prefix sum of the right half, then adding them.

/** * Maximum Subarray ā€” Divide & Conquer * T(n) = 2T(n/2) + O(n) ā†’ O(n log n) */ function maxSubArrayDC(nums, left = 0, right = nums.length - 1) { if (left === right) return nums[left]; const mid = Math.floor((left + right) / 2); // Best in left half, best in right half const leftBest = maxSubArrayDC(nums, left, mid); const rightBest = maxSubArrayDC(nums, mid + 1, right); // Best crossing the midpoint let leftSum = -Infinity, sum = 0; for (let i = mid; i >= left; i--) { sum += nums[i]; leftSum = Math.max(leftSum, sum); } let rightSum = -Infinity; sum = 0; for (let i = mid + 1; i <= right; i++) { sum += nums[i]; rightSum = Math.max(rightSum, sum); } const crossBest = leftSum + rightSum; return Math.max(leftBest, rightBest, crossBest); }
The divide-and-conquer approach runs in O(n log n) ā€” slower than Kadane's O(n). However, the cross-midpoint pattern (left suffix max + right prefix max) is a classic technique that shows up in segment trees and range query problems where you do need it.

7. Recognizing this pattern in other problems

Problem Recurrence Pattern
Maximum Subarray dp[i] = max(nums[i], dp[i-1] + nums[i]) 1D, depends on dp[i-1]
Maximum Product Subarray dpMax[i] = max(nums[i], dpMax[i-1]*nums[i], dpMin[i-1]*nums[i]) 1D, track both min and max
Maximum Sum Circular Subarray Kadane + Kadane on negated array + wrap-around 1D + circular trick
Best Time to Buy/Sell Stock dp[i] = max(dp[i-1], price[i] - minSoFar) 1D, depends on prefix min
House Robber dp[i] = max(dp[i-1], dp[i-2] + nums[i]) 1D, depends on dp[i-1] and dp[i-2]

The common thread: 1D DP with a "continue-or-restart" decision. The recurrence is always dp[i] = max(fresh_start, extend_previous) ā€” the only difference is what "extend" means in each context.

8. First-principles derivation checklist

When you see a "contiguous subarray" problem, ask:

  1. What does "ending at i" look like? ā€” Define dp[i] as the best answer for subarrays that must end at i. This constraint is what unlocks the recurrence.
  2. What's the choice at each position? ā€” For maximum subarray, it's "extend vs. fresh." For product subarray, it's "extend positive, extend negative, or fresh." The choice defines the recurrence.
  3. How many previous states do I need? ā€” If dp[i] depends only on dp[i-1], you have O(1) space. If it depends on dp[i-2] or a window, you need more.
  4. Is the answer dp[n-1] or max(dp[0..n-1])? ā€” For "ending at" DP, the answer is typically the maximum over all dp[i], not necessarily the last one.

9. Submissions ā€” click to expand

ā–¶ Submission #1 ā€” Explicit start-fresh / extend branches (first attempt) 2 bugs 6 issues
Click to expand

Your submitted code:

class Solution: def maxSubArray(self, nums: List[int]) -> int: # State a_start = 0 a_end = 0 max_sum = nums[0] cur_sum = nums[0] for idx in range(1, len(nums)): n = nums[idx] # if cur_sum is negative - better to start a fresh array if cur_sum < 0: a_start = idx a_end = idx max_sum = n ā† BUG #1: unconditionally overwrites global max cur_sum = n else: # if it's positive - then include it ā† Issue: ambiguous indentation new_sum = cur_sum + n if new_sum > max_sum: a_end = idx max_sum = new_sum cur_sum = new_sum print(f"Maximum subarray: {nums[a_start:a_end+1]}") print(f"Max sum: {max_sum}") return max_sum
Interviewer verdict: Would not pass 1 critical logic bug hides behind a deceptively correct structure

šŸ”“ Blocking Bugs

Bug #1 ā€” max_sum = n destroys the global maximum BLOCKING

Every time cur_sum < 0, you reset max_sum = n without comparing against the existing best. This means if the previously found global maximum is larger than the fresh-start element, you throw it away.

Counterexample: [2, -3, 1]

Step idx nums[idx] cur_sum (before) Branch max_sum (after) Correct max
init 0 2 ā€” ā€” 2 2
1 1 -3 2 else (extend) 2 2
2 2 1 -1 if (fresh) 1 2

At idx=2, cur_sum = -1 < 0 ā†’ enters the fresh branch ā†’ max_sum = 1. The correct answer is 2 (the element at index 0 alone). Your code returns 1.

āš ļø This bug is easy to miss because it only fires when: (a) cur_sum goes negative, AND (b) the fresh-start element is smaller than a previous best. Many test cases never trigger (a) because they're overwhelmed with positive numbers.

Fix:
max_sum = max(max_sum, n) ā€” the global max should never decrease
Bug #2 ā€” a_start / a_end corrupted by the same overwrite BLOCKING

When Bug #1 fires, the tracking variables a_start and a_end are reset to the fresh-start position even though that new subarray doesn't beat the old best. This means:

  • The print at the bottom reports the wrong subarray
  • If anyone extended this code to return the subarray (instead of just the sum), it would be silently wrong
  • The tracking variables disagree with max_sum ā€” a classic invariant violation

In the [2, -3, 1] counterexample: a_start=2, a_end=2 but max_sum should be 2 (from index 0). The tracking says [1] is the answer, which contradicts the correct answer [2].

Fix:
Only update a_start/a_end when the fresh-start actually beats the existing max_sum:
if n > max_sum: a_start = a_end = idx; max_sum = n

šŸŸ” Design / Code Quality Issues

Issue #3 ā€” Debug print statements in production submission

LeetCode doesn't penalize print(), but in a real interview or code review, debug scaffolding left in the final answer signals carelessness. If the problem asked for the subarray itself, the prints would be a substitute for a proper return value ā€” which isn't what was asked.

Issue #4 ā€” Variable n shadows conventional meaning

n is universally used for array length. Using it for the current element is confusing ā€” especially when len(nums) appears nearby. An interviewer will ask: "what does n represent here?" Use num or x.

Issue #5 ā€” Inverted condition structure

You test if cur_sum < 0 (the bad case) first and else (the good case) second. The canonical Kadane tests if cur_sum > 0 (extend) / else (fresh). Your version is functionally equivalent but reads as "when things are bad, do X; otherwise, Y" ā€” which forces the reader to invert the logic mentally. Always put the affirmative branch first:

# Canonical: test the good case first if cur_sum > 0: cur_sum += num # extend ā€” the natural, desirable action else: cur_sum = num # start fresh ā€” the fallback max_sum = max(max_sum, cur_sum)
Issue #6 ā€” Ambiguous comment indentation inside else:

This is subtle but it's exactly the kind of thing a strict reviewer flags:

else: # if it's positive - then include it new_sum = cur_sum + n

The comment is indented to the same level as else: (12 spaces), while new_sum is at 16 spaces. Python technically accepts this ā€” comments are ignored by the parser and don't affect block structure. But every human reader will do a double-take wondering if this is a syntax error. The comment should be inside the block:

else: # cur_sum >= 0 ā€” extending is beneficial or neutral new_sum = cur_sum + n
Issue #7 ā€” a_start never updated during extension

When the else branch finds new_sum > max_sum, you update a_end = idx but never touch a_start. This happens to work because a_start was set when you entered the current subarray (the last time you started fresh). But this is an implicit invariant ā€” the code doesn't state it, so a future refactor could break it. Explicitly tracking where the current subarray begins (separate from where the best subarray begins) is clearer:

curr_start = 0 # where the current running subarray starts for idx, num in enumerate(nums[1:], 1): if cur_sum > 0: cur_sum += num else: cur_sum = num curr_start = idx # fresh subarray begins here if cur_sum > max_sum: max_sum = cur_sum a_start = curr_start a_end = idx
Issue #8 ā€” Subarray tracking is premature for the problem

LeetCode 53 asks for the sum only. Adding a_start, a_end, and print() to reconstruct the subarray is a feature the problem doesn't ask for. In an interview, this is neutral-to-positive if you get it right. But when tracking variables contain bugs (Issue #2, #7), the extra complexity becomes a liability ā€” it introduces failure modes for something that wasn't required. Ship the simplest correct solution first, then extend.

šŸŸ¢ Fixed & Improved Solution

What changed and why:
  • Fixed the overwrite: max_sum is never decremented ā€” always max(max_sum, ...)
  • Flipped the condition: test cur_sum > 0 (extend) first, else (fresh) second
  • Removed a_start/a_end: the problem asks for the sum, not the subarray
  • Renamed n ā†’ num: no shadowing, clear meaning
  • Removed print(): clean production code
  • Unified max_sum update: single max(max_sum, cur_sum) after each step ā€” no duplicated logic across branches
class Solution: def maxSubArray(self, nums: List[int]) -> int: max_sum = cur_sum = nums[0] for num in nums[1:]: # Extend if beneficial, otherwise start fresh if cur_sum > 0: cur_sum += num else: cur_sum = num # Single point of truth for the global max max_sum = max(max_sum, cur_sum) return max_sum

Or even shorter ā€” the one-liner recurrence that's standard in interviews:

class Solution: def maxSubArray(self, nums: List[int]) -> int: max_sum = cur_sum = nums[0] for num in nums[1:]: cur_sum = max(num, cur_sum + num) max_sum = max(max_sum, cur_sum) return max_sum

šŸŽÆ Key Takeaway

You clearly understand Kadane's core idea ā€” the extend-vs-fresh decision. The explicit if/else branching proves you've internalized the recurrence. The attempt to track subarray bounds shows ambition beyond the minimum requirement.

But Bug #1 is a classic DP mistake: updating the global optimum inside a conditional branch without a max() guard. This pattern ā€” "I know I found a new candidate, so it must be better" ā€” is exactly how DP solutions fail in interviews. The fix is mechanical: never let max_sum decrease. Every write to it must pass through max() or a comparison guard.

  • Single source of truth for max: pull the max_sum = max(max_sum, cur_sum) out of the branches. One line, unconditional, after each step. Guarantees correctness.
  • Test negative-interleaved arrays: [2, -3, 1], [5, -10, -1], [-2, 1, -3, 4]. These expose the "fresh start destroys best" bug.
  • If you track auxiliary state, verify the invariant: max_sum must always equal the max of all subarrays ending at or before the current index. If tracking variables disagree, one of them is wrong.
  • Canonical form matters in interviews: cur_sum = max(num, cur_sum + num) says in one line what your if/else says in six. Both are correct, but the one-liner signals fluency.
ā–¶ Submission #2 ā€” Ternary + comparison guard (second attempt) 1 bug 5 issues 1 improvement
Click to expand
Progress from #1: Improved but regressed Fixed the critical logic bug, but silently broke subarray tracking entirely

What you fixed: āœ… Bug #1 (max_sum overwrite) ā€” killed. āœ… Unified extend/fresh into a single ternary. āœ… max_sum now only updates via a guard comparison.
What regressed: āŒ a_start is never updated at all ā€” it was at least set in the fresh branch of #1, now it's frozen at 0 forever.

Your submitted code:

class Solution: def maxSubArray(self, nums: List[int]) -> int: # State a_start = 0 a_end = 0 max_sum = nums[0] cur_sum = nums[0] for idx in range(1, len(nums)): n = nums[idx] # if cur_sum is negative - better to start a fresh array new_sum = n if cur_sum < 0 else cur_sum + n āœ… cleaner than #1's if/else if new_sum > max_sum: āœ… guarded comparison ā€” overwrite bug is gone a_end = idx max_sum = new_sum ā† ISSUE: a_start never updated here or anywhere cur_sum = new_sum print(f"Maximum subarray: {nums[a_start:a_end+1]}") print(f"Max sum: {max_sum}") return max_sum

šŸ”“ Blocking Bug

Bug #1 ā€” a_start is dead code ā€” never written after initialization BLOCKING regression from #1

In submission #1, a_start was at least set inside the if cur_sum < 0 branch (even if it had the overwrite bug). In this submission, a_start is never updated at all. It stays frozen at 0 forever.

Why this is worse than #1: In #1, the tracking was sometimes right (when the overwrite bug didn't fire). Here, it's always wrong for any input where the best subarray doesn't start at index 0.

Trace through the main example: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

idx num cur_sum (before) new_sum new best? a_start (after) a_end (after) max_sum printed subarray
0 -2 ā€” ā€” ā€” 0 0 -2 [-2]
1 1 -2 1 (fresh) āœ“ 0 1 1 [-2, 1] ā† WRONG
... ... ... ... ... 0 6 ... ...
final ā€” ā€” ā€” ā€” 0 6 6 [-2,1,-3,4,-1,2,1] sum=2 ā† WRONG

The print at the bottom reports the subarray [-2, 1, -3, 4, -1, 2, 1] (indices 0ā€“6, sum = 2), but max_sum = 6. The correct subarray is [4, -1, 2, 1] (indices 3ā€“6). The tracking variables disagree with the returned answer.

Fix: Track curr_start separately from best_start

You need two concepts: where the current running subarray begins (updates on every fresh start), and where the best subarray begins (only updates when a new max is found):

curr_start = 0 # beginning of the current running subarray for idx in range(1, len(nums)): num = nums[idx] new_sum = num if cur_sum < 0 else cur_sum + num if cur_sum < 0: curr_start = idx # fresh subarray starts here if new_sum > max_sum: a_start = curr_start # snapshot the start of the best so far a_end = idx max_sum = new_sum cur_sum = new_sum

šŸŸ” Design / Code Quality Issues

Issue #2 ā€” a_start is dead code with a misleading name

A variable named a_start that is initialized, never modified, and always reads as 0 is a red flag. It signals either: (a) the tracking logic was removed during refactoring, or (b) the variable was added with intent that was never implemented. Either way, dead code in a 15-line function is hard to justify.

Issue #3 ā€” print output is now actively misleading

In submission #1, the prints were sometimes wrong. In submission #2, they're always wrong (unless the best subarray happens to start at index 0). Debug output that contradicts the returned answer is worse than no output ā€” it would send anyone debugging this code down the wrong path. Simply remove the prints.

Issue #4 ā€” Same n shadowing from #1

Unchanged. n = nums[idx] still shadows the array-length convention. Use num or x.

Issue #5 ā€” Same inverted condition from #1

n if cur_sum < 0 else cur_sum + n ā€” the ternary tests the negative case first. While compact, cur_sum + num if cur_sum > 0 else num reads left-to-right as "extend if beneficial, else fresh" and matches how a human thinks about the problem.

Issue #6 ā€” The comment is now a lie

# if cur_sum is negative - better to start a fresh array describes behavior that happens implicitly inside the ternary, but the ternary also handles the non-negative case with an else. The comment only describes half the logic. Either remove it or say what the line actually does: # extend if beneficial, otherwise restart.

šŸ”µ What Improved from #1

Improvement ā€” The ternary is genuinely better

The collapse of 6 lines of if/else into one ternary is the right instinct. Compare:

# Submission #1 ā€” 6 lines, duplicated max_sum update if cur_sum < 0: a_start = idx a_end = idx max_sum = n ā† bug: unconditional overwrite cur_sum = n else: new_sum = cur_sum + n if new_sum > max_sum: a_end = idx max_sum = new_sum cur_sum = new_sum # Submission #2 ā€” 4 lines, single max_sum guard new_sum = n if cur_sum < 0 else cur_sum + n if new_sum > max_sum: a_end = idx max_sum = new_sum cur_sum = new_sum

This is cleaner, less error-prone, and closer to the canonical form. The direction is right ā€” now just finish the job.

šŸŸ¢ Fixed & Improved Solution

Minimal fix ā€” preserve your ternary style, fix tracking, drop prints:
class Solution: def maxSubArray(self, nums: List[int]) -> int: max_sum = cur_sum = nums[0] for num in nums[1:]: # Extend if beneficial; otherwise start fresh cur_sum = cur_sum + num if cur_sum > 0 else num max_sum = max(max_sum, cur_sum) return max_sum

If you really want subarray tracking (not required by the problem, but good practice):

class Solution: def maxSubArray(self, nums: List[int]) -> int: max_sum = cur_sum = nums[0] best_start = best_end = curr_start = 0 for idx, num in enumerate(nums[1:], 1): if cur_sum > 0: cur_sum += num else: cur_sum = num curr_start = idx # fresh subarray starts here if cur_sum > max_sum: max_sum = cur_sum best_start = curr_start # snapshot: this is the best we've seen best_end = idx return max_sum # or return nums[best_start:best_end+1] if asked

šŸŽÆ Key Takeaway

You fixed the big bug and made the code more concise ā€” that's real progress. The ternary is the right refactoring direction. The max_sum guard is correct now.

But you dropped the a_start update entirely. When you refactor an if/else into a ternary, check whether every side effect from the original branches was preserved. The fresh branch in #1 set a_start ā€” when that branch disappeared into the ternary, the assignment disappeared too.

  • Refactoring rule: when collapsing branches, list every mutation that happened in each branch and verify each one is still handled.
  • Two-start tracking: curr_start (where the current subarray begins) vs. best_start (where the best subarray begins). These update at different times ā€” confusing them is the root of this bug.
  • Drop dead code or fix it: a_start is now dead. Either remove it (if you're only returning the sum) or wire it up correctly (if you're tracking). A dead variable is worse than no variable.
  • You're one line away: cur_sum = cur_sum + num if cur_sum > 0 else num; max_sum = max(max_sum, cur_sum). That's the whole algorithm in two lines.