1. First state
The best subarray ending at index 0 is nums[0].
let bestEndingHere = nums[0]Typorithm · easy
Maximum Subarray
▷ Interactive algorithm labmaximum-subarray-dpdynamic-programmingkadanespace-optimized
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Maximum Subarray
Dynamic Programming
Maximum Subarray uses Kadane's DP: keep the best sum ending here and the best sum seen so far.
A negative previous sum may hurt the current subarray.
The transition chooses extend or restart.
A global best stores the answer across all endings.
Preparing algorithm lab…
01
State: best sum ending at i.
02
Transition: max(nums[i], previous + nums[i]).
03
Answer: best global sum.
04
Time O(n), space O(1).
function maxSubArray(nums) {
let bestEndingHere = nums[0];
let bestSoFar = nums[0];
for (let i = 1; i < nums.length; i++) {
bestEndingHere = Math.max(nums[i], bestEndingHere + nums[i]);
bestSoFar = Math.max(bestSoFar, bestEndingHere);
}
return bestSoFar;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Extend or restart
Either start fresh at nums[i] or extend the previous subarray.
bestEndingHere = Math.max(nums[i], bestEndingHere + nums[i])3. Global best
Track the best subarray seen anywhere.
bestSoFar = Math.max(bestSoFar, bestEndingHere)A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.