Maximum Subarray
Understand the problem
Given an array nums (it may contain negative numbers). Find the contiguous subarray with the largest sum and return that sum.
Example:
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
// the subarray [4, -1, 2, 1] has sum 6 — the largest
output = 6The subarray must be contiguous (you cannot skip elements in the middle) and contain at least 1 element.
Show the basic approach (slower)
O(n²) time, O(1) spacefunction maxSubArray(nums: number[]): number {
let best = -Infinity
for (let i = 0; i < nums.length; i++) {
let sum = 0
for (let j = i; j < nums.length; j++) {
sum += nums[j]
best = Math.max(best, sum)
}
}
return best
}Try every start i and accumulate up to every end j.
Correct, but with n=10⁵ that is n² = 10¹⁰ additions — far too slow.
Optimal solution
O(n) time, O(1) spacefunction maxSubArray(nums: number[]): number {
let curr = nums[0] // best subarray sum ENDING at i
let best = nums[0]
for (let i = 1; i < nums.length; i++) {
curr = Math.max(nums[i], curr + nums[i])
best = Math.max(best, curr)
}
return best
}The optimal solution is Kadane's algorithm.
- At each position, ask: should we extend the previous run (
curr + nums[i]) or start over fromnums[i]itself? Ifcurris negative it only drags the total down, so drop it and start fresh.bestrecords the largest value seen so far. - It is a greedy idea: immediately discard any prefix whose sum is negative.
Step-by-step trace
1function maxSubArray(nums: number[]): number {2 let curr = nums[0] // best subarray sum ENDING at i3 let best = nums[0]4 for (let i = 1; i < nums.length; i++) {5 curr = Math.max(nums[i], curr + nums[i])6 best = Math.max(best, curr)7 }8 return best9}Edge cases to remember
An all-negative array ([-3, -1, -2]) → the answer is the largest negative number (−1), NOT 0.
That is why you initialize with nums[0] and must not initialize best = 0.
A single-element array → return that element.
Initializing
curr = 0and then adding is a trap: an all-negative array would wrongly return 0.You must compare
Math.max(nums[i], curr + nums[i]).A 0 in between does not reset the run — only a negative sum means you should start over.