Maximum Subarray (LeetCode 53)
You're given an integer array nums. A subarray is any non-empty run of elements sitting next to each other in the array, with no skipping.
Scan every possible subarray and return the largest sum any of them adds up to.
Worked Examples
nums = [-2,1,-3,4,-1,2,1,-5,4]6nums = [1]1nums = [5,4,-1,7,8]23⚖️Formal Constraints & Bounds
1 <= nums.length <= 105-104 <= nums[i] <= 104
Core Insight
Negative running prefix sums are dropped immediately to maximize downstream totals.
Real-World Scenario & Production Applications
Maximum profit period in stock price differentials, high-intensity signal interval detection.
Subproblems & Recurrence Decomposition3 Phases
At each element nums[i], decide whether to extend the existing contiguous subarray (curr_sum + nums[i]) or discard a negative prefix and start fresh at nums[i].
curr_sum = max(nums[i], curr_sum + nums[i])Step-by-Step Execution Trace Table
| Element x | curr_sum = max(x, curr+x) | best_sum | Subarray State |
|---|---|---|---|
| -2 | -2 | -2 | [-2] |
| 1 | 1 | 1 | [1] (Reset) |
| -3 | -2 | 1 | [1, -3] |
| 4 | 4 | 4 | [4] (Reset) |
| -1 | 3 | 4 | [4, -1] |
| 2 | 5 | 5 | [4, -1, 2] |
| 1 | 6 | 6 | [4, -1, 2, 1] |
| 1 | curr = best = nums[0] |
| 2 | for x in nums[1:]: |
| 3 | curr = max(x, curr + x) |
| 4 | best = max(best, curr) |
| 5 | return best |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Kadane's algorithm resolves the maximum contiguous subarray sum in a single linear pass. At each index $i$, the optimal contiguous subarray ending at $i$ either extends the previous subarray ($current_sum + nums[i]$) or discards negative accumulated baggage to start fresh at $nums[i]$: $current_sum = \max(nums[i], current_sum + nums[i])$. Tracking the maximum of these local values yields the global maximum in $O(N)$ time and $O(1)$ space. 🎒 The Analogy: Dropping a Negative Running Total Mid-Hike
Imagine carrying a running total of "profit so far" as you walk a trail collecting and losing money at each step. If your running total ever goes negative, carrying it forward into the next step can only lower whatever you collect next. So the moment your total dips below zero, you drop it entirely and start fresh from the next step, as if today were day one. If your total is still positive, it's still an asset worth carrying forward.
🔑 The Key Idea in the Code
curr and best answer two different questions: curr is "the best subarray ending right here," which can reset at any point, while best is "the best subarray seen anywhere so far," which only ever grows. Losing track of this distinction is the most common bug when writing Kadane's from memory.
All-negative array sentinel reset: Initializing
max_sum = 0. Ifnums = [-3, -2, -1], resetting to 0 returns 0 instead of-1. Initializemax_sum = nums[0].Resetting current sum before updating global max: Resetting
curr = max(0, curr)before evaluatingmax_sum = max(max_sum, curr). On all-negative arrays, this corrupts the answer. Always computecurr = max(x, curr + x)first.Confusing contiguous subarray with subsequence: A subarray must be contiguous; sorting the array or skipping negative numbers to pick positive values violates problem constraints.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Max contiguous subarray sum with negative and positive values.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: curr is the best sum of a subarray that ends at the current index, and best is the largest curr seen so far.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Comparing
curr + xwith 0 instead of withx: this allows an empty subarray.Returning curr instead of best: the best subarray can end before the last number.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I start with
curr = best = nums[0]. For each numberxinnums[1:], I updatecurr = max(x, curr + x)andbest = max(best, curr). I returnbest. Runs inO(N)time andO(1)space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: Kadane's algorithm: curr_max = max(nums[i], curr_max + nums[i]). If running sum drops below 0, resets with current element. Single pass through N elements.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Only stores curr_max and global_max scalar variables.
T(N) = N · O(1) = O(N)
Derivation Progression
Si = max(nums[i], Si-1 + nums[i])
Extends previous subarray or starts fresh at nums[i] if previous sum was negative.
M = max(M, Si)
Updates best seen subarray sum in O(1).
N iterations = O(N)
Examines each array value exactly once.
Variable Definitions
Total number of elements in the array
Memory Architecture & Bounds
O(1) Iterative
O(1) Two scalar registers
O(1) Max sum integer
Boundary Best / Worst Cases
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "subarray with the largest sum". Kadane's Algorithm: at each position, decide whether to append current element to the existing running sum OR restart a new subarray from the current element.
. Strictly linear time single pass.
All negative numbers (e.g. [-3, -2, -5]): initializing max_sum = 0 produces false answers; must initialize max_sum = nums[0].
Maximum Subarray (LeetCode 53)
You're given an integer array nums. A subarray is any non-empty run of elements sitting next to each other in the array, with no skipping.
Scan every possible subarray and return the largest sum any of them adds up to.
Worked Examples
nums = [-2,1,-3,4,-1,2,1,-5,4]6nums = [1]1nums = [5,4,-1,7,8]23⚖️Formal Constraints & Bounds
1 <= nums.length <= 105-104 <= nums[i] <= 104
Core Insight
Negative running prefix sums are dropped immediately to maximize downstream totals.
Real-World Scenario & Production Applications
Maximum profit period in stock price differentials, high-intensity signal interval detection.
Subproblems & Recurrence Decomposition3 Phases
At each element nums[i], decide whether to extend the existing contiguous subarray (curr_sum + nums[i]) or discard a negative prefix and start fresh at nums[i].
curr_sum = max(nums[i], curr_sum + nums[i])Step-by-Step Execution Trace Table
| Element x | curr_sum = max(x, curr+x) | best_sum | Subarray State |
|---|---|---|---|
| -2 | -2 | -2 | [-2] |
| 1 | 1 | 1 | [1] (Reset) |
| -3 | -2 | 1 | [1, -3] |
| 4 | 4 | 4 | [4] (Reset) |
| -1 | 3 | 4 | [4, -1] |
| 2 | 5 | 5 | [4, -1, 2] |
| 1 | 6 | 6 | [4, -1, 2, 1] |
| 1 | curr = best = nums[0] |
| 2 | for x in nums[1:]: |
| 3 | curr = max(x, curr + x) |
| 4 | best = max(best, curr) |
| 5 | return best |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Kadane's algorithm resolves the maximum contiguous subarray sum in a single linear pass. At each index $i$, the optimal contiguous subarray ending at $i$ either extends the previous subarray ($current_sum + nums[i]$) or discards negative accumulated baggage to start fresh at $nums[i]$: $current_sum = \max(nums[i], current_sum + nums[i])$. Tracking the maximum of these local values yields the global maximum in $O(N)$ time and $O(1)$ space. 🎒 The Analogy: Dropping a Negative Running Total Mid-Hike
Imagine carrying a running total of "profit so far" as you walk a trail collecting and losing money at each step. If your running total ever goes negative, carrying it forward into the next step can only lower whatever you collect next. So the moment your total dips below zero, you drop it entirely and start fresh from the next step, as if today were day one. If your total is still positive, it's still an asset worth carrying forward.
🔑 The Key Idea in the Code
curr and best answer two different questions: curr is "the best subarray ending right here," which can reset at any point, while best is "the best subarray seen anywhere so far," which only ever grows. Losing track of this distinction is the most common bug when writing Kadane's from memory.
All-negative array sentinel reset: Initializing
max_sum = 0. Ifnums = [-3, -2, -1], resetting to 0 returns 0 instead of-1. Initializemax_sum = nums[0].Resetting current sum before updating global max: Resetting
curr = max(0, curr)before evaluatingmax_sum = max(max_sum, curr). On all-negative arrays, this corrupts the answer. Always computecurr = max(x, curr + x)first.Confusing contiguous subarray with subsequence: A subarray must be contiguous; sorting the array or skipping negative numbers to pick positive values violates problem constraints.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Max contiguous subarray sum with negative and positive values.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: curr is the best sum of a subarray that ends at the current index, and best is the largest curr seen so far.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Comparing
curr + xwith 0 instead of withx: this allows an empty subarray.Returning curr instead of best: the best subarray can end before the last number.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I start with
curr = best = nums[0]. For each numberxinnums[1:], I updatecurr = max(x, curr + x)andbest = max(best, curr). I returnbest. Runs inO(N)time andO(1)space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: Kadane's algorithm: curr_max = max(nums[i], curr_max + nums[i]). If running sum drops below 0, resets with current element. Single pass through N elements.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Only stores curr_max and global_max scalar variables.
T(N) = N · O(1) = O(N)
Derivation Progression
Si = max(nums[i], Si-1 + nums[i])
Extends previous subarray or starts fresh at nums[i] if previous sum was negative.
M = max(M, Si)
Updates best seen subarray sum in O(1).
N iterations = O(N)
Examines each array value exactly once.
Variable Definitions
Total number of elements in the array
Memory Architecture & Bounds
O(1) Iterative
O(1) Two scalar registers
O(1) Max sum integer
Boundary Best / Worst Cases
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "subarray with the largest sum". Kadane's Algorithm: at each position, decide whether to append current element to the existing running sum OR restart a new subarray from the current element.
. Strictly linear time single pass.
All negative numbers (e.g. [-3, -2, -5]): initializing max_sum = 0 produces false answers; must initialize max_sum = nums[0].