March 24
Maximum Subarray
How to notice that the real question is whether the previous sum still helps or whether it is now hurting.
Arrays and Dynamic Programming Beginner 18 min TypeScript
Given an integer array nums, find the contiguous subarray with the largest sum and return that sum.
Example:
Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
The subarray [4, -1, 2, 1] has sum 6.
What to notice before coding
- The subarray must be contiguous. You cannot skip elements.
- The answer can be a single element.
- If every number is negative, the best answer still exists.
Common mistakes
- summing only positive numbers and forgetting the subarray must stay contiguous
- resetting to `0` and breaking the all-negative case
Step 1 — Understand the one word that changes everything
The prompt says contiguous subarray.
That kills a common bad reading: picking scattered numbers that look good and adding them together.
You cannot skip.
The answer has to be one continuous block.
Step 2 — Write the correct baseline
A good baseline is to test every possible subarray, while summing incrementally:
export function maxSubArray(nums: number[]): number {
let best = -Infinity
for (let start = 0; start < nums.length; start += 1) {
let sum = 0
for (let end = start; end < nums.length; end += 1) {
sum += nums[end]
best = Math.max(best, sum)
}
}
return best
}
It works. But it still tests every start against every end.
Step 3 — Ask what matters at the current position
When you reach nums[i], what do you want to know?
You do not need the best sum of the whole array yet.
The local question is:
what is the best subarray sum that ends exactly here?
That leads to the key idea:
- if the previous sum helps, keep it
- if the previous sum hurts, restart at the current value
Step 4 — Store the best sum ending here
That becomes a very simple recurrence:
bestEndingHere = max(value, bestEndingHere + value)
Then compare that with the best global answer.
That is the whole idea behind Kadane.
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function maxSubArray(nums: number[]): number {
// your solution here
return 0
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(n)
Space: O(1)
Solution 1 — Test all subarrays O(n²)
A decent baseline is to fix the start and keep extending the end.
export function maxSubArray(nums: number[]): number {
let best = -Infinity
for (let start = 0; start < nums.length; start += 1) {
let sum = 0
for (let end = start; end < nums.length; end += 1) {
sum += nums[end]
best = Math.max(best, sum)
}
}
return best
}Correct, but still quadratic.
Solution 2 — Kadane O(n)
If the local question is “what is the best sum ending here?”, one pass is enough.
export function maxSubArray(nums: number[]): number {
let bestEndingHere = nums[0]
let bestOverall = nums[0]
for (let index = 1; index < nums.length; index += 1) {
const value = nums[index]
bestEndingHere = Math.max(value, bestEndingHere + value)
bestOverall = Math.max(bestOverall, bestEndingHere)
}
return bestOverall
}The algorithm looks short because the question was reduced to the right state.
What to say in the interview
A strong short explanation would be:
The baseline tests all subarrays and costs
O(n²). The optimized version stores the best subarray sum ending at the current index. If the previous sum helps, I keep it. If it hurts, I restart at the current value. That reduces the problem toO(n).
That shows that you:
- respected the contiguity constraint
- turned a global problem into a local one
- explained Kadane as reasoning, not a memorized name
When this pattern shows up again
Many people describe Kadane as a form of dynamic programming with tiny state.
In some explanations, it also feels greedy, because the local choice to continue or restart is exactly what keeps the best running segment alive.
The same pattern comes back when you need to:
- decide whether to continue or restart
- keep a best local answer while scanning
- compress dynamic programming into tiny state
- explain why a local decision works
The point is not memorizing “Kadane.”
The point is noticing when the right state is “best answer ending here.”