Znajduje maksymalną sumę spójnego (ciągłego) podciągu w O(n), śledząc najlepszą sumę „kończącą się tutaj” i najlepszą globalnie.
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;
}