It finds the maximum sum of a contiguous subarray in O(n) time by tracking the best sum ending at the current position and the best overall.
function maxSubarraySum(nums: number[]): number {
let best = nums[0];
let cur = nums[0];
for (let i = 1; i < nums.length; i++) {
cur = Math.max(nums[i], cur + nums[i]);
best = Math.max(best, cur);
}
return best;
}Kadane’s algorithm is DP in one pass.
Let:
Transition:
If extending the previous subarray makes things worse, you restart at i.