You're looking at a row of daily profit-and-loss numbers for a trading desk: some days you gained, some days you lost. You want the single best streak — a run of consecutive days whose net total is the highest possible. You can't skip a bad day in the middle and stitch two good runs together; the run has to be unbroken. Given an array of numbers (positive, negative, or zero), arrayMaximumSumContiguous(nums) returns the largest sum obtainable from any contiguous, non-empty slice of that array. This is the classic maximum subarray problem, solved optimally by Kadane's algorithm.
function arrayMaximumSumContiguous(nums: number[]): number;
// returns the largest sum of any contiguous, non-empty subarray.
// the subarray must be a single unbroken run — no skipping elements.// A mix of gains and losses. The best run is [4, -1, 2, 1], summing to 6.
// Taking the 4 alone gives only 4; dipping through -1 to reach 2 and 1 pays off,
// but the -5 just after is too costly to cross to reach the trailing 4.
arrayMaximumSumContiguous([-2, 1, -3, 4, -1, 2, 1, -5, 4]); // 6// Every number is negative. There's no way to reach a positive sum, and an
// empty run isn't allowed — so the answer is the single least-bad element, -1.
arrayMaximumSumContiguous([-8, -3, -6, -1, -7]); // -1[1, 3] from [1, 2, 3] is not contiguous; [1, 2] and [2, 3] are.[-8, -3, -1] the answer is -1, never 0.0. When nums is [], there is no element to pick; this implementation defines the answer as 0. (Some variants throw instead — we pick 0 here and the tests pin it down. If your contract differs, change this one line and its test.)[5] is 5; [-5] is -5.You'll find the largest sum reachable from any single unbroken run of an array, in one pass, by tracking just two running numbers.
You have a row of numbers — think of them as daily profits and losses on a trading desk. Some days you gain, some you lose. You want the single best streak: a run of consecutive days whose net total is as high as it can be. You're not allowed to cherry-pick the good days and drop the bad ones from the middle — the run has to be one continuous stretch. So the question becomes: where do you start the run, and where do you stop, to walk away with the most?
The slippery parts are the negatives. A losing day inside a great streak might still be worth crossing if the days around it more than make up for it. But a huge loss in the middle can be bad enough that nothing on the far side is worth reaching back across — at that point you're better off forgetting the past and starting a fresh run. Knowing when to carry a bad day forward and when to cut your losses is the whole problem.
Here's the array we'll keep coming back to: [-2, 1, -3, 4, -1, 2, 1, -5, 4]. The best contiguous run is [4, -1, 2, 1], which totals 6. Notice it includes a negative (-1) — crossing that loss was worth it because 4 before it and 2 + 1 after it more than paid for it. But the run stops before the -5: that loss is too steep, and the lone 4 at the end can't claw it back.
The key insight that unlocks the fast solution: as you scan left to right, the only question that matters at each element is "what's the best run that ends right here?" If you know that for every position, the overall answer is just the largest of those per-position bests. And the best run ending at position i has only two shapes: either it's just the element nums[i] standing alone, or it's nums[i] glued onto the best run ending at i - 1. You pick whichever is larger.
The obvious approach mirrors the problem statement directly: a run is defined by where it starts and where it ends, so try every (start, end) pair, add up the elements between them, and keep the biggest total.
function maxSubarrayBrute(nums) {
if (nums.length === 0) return 0;
let best = -Infinity;
for (let start = 0; start < nums.length; start++) {
let sum = 0;
for (let end = start; end < nums.length; end++) {
sum += nums[end]; // extend the run one element to the right
if (sum > best) best = sum; // every (start, end) is a candidate
}
}
return best;
}This is correct. Seeding best with -Infinity (not 0) is what makes it return the largest single element on an all-negative array instead of a bogus 0 — every real sum beats -Infinity, so the closest-to-zero element wins. The inner loop reuses its running sum rather than re-adding from scratch, so it's O(n²), not O(n³). But O(n²) still means that for an array of 10,000 numbers you're doing roughly 50 million additions — and you're recomputing overlapping sums you've already seen. There's structure here we're throwing away.
The structure we threw away: when you slide the run's end one step to the right, the best run ending at the new position is almost entirely determined by the best run ending at the previous position. You don't need to re-examine every possible start. This is Kadane's algorithm.
function arrayMaximumSumContiguous(nums) {
// Documented contract: an empty array has no element to pick, so we
// define its answer as 0. (Swap this for `throw` if your spec differs.)
if (nums.length === 0) return 0;
// Seed BOTH trackers with the first element, not 0. The run must be
// non-empty, so the smallest possible answer is a single element —
// seeding with 0 would wrongly let an all-negative array return 0.
let bestEndingHere = nums[0]; // best run that must end at the current index
let bestSoFar = nums[0]; // best run seen anywhere so far
for (let i = 1; i < nums.length; i++) {
const x = nums[i];
// Either start fresh at x, or extend the previous run by x —
// whichever is larger. This single line is the reset decision.
bestEndingHere = Math.max(x, bestEndingHere + x);
// The global answer is the best ending-here we've ever seen.
bestSoFar = Math.max(bestSoFar, bestEndingHere);
}
return bestSoFar;
}
module.exports = { arrayMaximumSumContiguous };Two variables, one pass, O(n) time and O(1) extra space. The shift from the naive version is the line bestEndingHere = Math.max(x, bestEndingHere + x). Read it as a fork in the road at every element: is the run I've been building still helping me? If bestEndingHere is positive, carrying it forward (bestEndingHere + x) beats starting over, so you extend. If it's negative, it's a debt — x alone is bigger than x plus a negative — so you abandon the old run and reset to just x. You never have to look back at where the run started; the previous bestEndingHere already summarises everything to the left that's worth keeping.
Why two variables and not one? bestEndingHere is local and volatile — it rises and falls and resets as the scan moves. bestSoFar is a high-water mark that only ever goes up. If you tried to return bestEndingHere, you'd report the best run ending at the last element, which is usually not the best run overall. You have to snapshot the peak as you pass it, because the scan will keep moving and may reset right after the best run ends.
Let's trace a small array built to show the reset: [3, -1, 4, -10, 2]. The best run is the front [3, -1, 4] = 6; the -10 is a wall that resets everything after it.
init bestEndingHere = 3, bestSoFar = 3 (both seeded with nums[0])
i=1, x=-1 max(-1, 3 + -1) = max(-1, 2) = 2 → extend (carry was positive)
bestEndingHere = 2, bestSoFar = max(3, 2) = 3
i=2, x=4 max(4, 2 + 4) = max(4, 6) = 6 → extend
bestEndingHere = 6, bestSoFar = max(3, 6) = 6 ← new peak
i=3, x=-10 max(-10, 6 + -10) = max(-10, -4) = -4 → carry (both are awful,
bestEndingHere = -4, bestSoFar = max(6, -4) = 6 -4 still beats -10)
i=4, x=2 max(2, -4 + 2) = max(2, -2) = 2 → RESET (carrying the -4 debt
bestEndingHere = 2, bestSoFar = max(6, 2) = 6 is worse than 2 alone)
return 6
The decisive moment is i=4. The running sum had gone underwater to -4 after the -10. When x = 2 arrives, bestEndingHere + x is -2, but x alone is 2. Kadane takes the larger — it resets, throwing away the -10 and everything before it, because no run that has to drag the -10 along can ever be the winner. Meanwhile bestSoFar never dropped: it locked in 6 back at i=2 and held it. That's exactly why you need the second variable.
0 on an all-negative array. This is the single most common bug. It happens when you seed bestSoFar = 0 (or write Math.max(0, ...) anywhere). On [-3, -1, -2] the true answer is -1, the least-bad single element — but a 0 seed reports 0, a sum no non-empty run can actually produce. Seed with nums[0] instead, so the trackers start from a real element.bestEndingHere to 0 instead of Math.max(x, bestEndingHere + x). A popular but broken variant does bestEndingHere = Math.max(0, bestEndingHere + x) to "drop negative runs." That secretly assumes the empty run (sum 0) is allowed, so it also returns 0 on all-negative input. The correct reset floor is x itself, never 0 — the run must always contain at least the current element.i = 0. Because you seed both trackers with nums[0], the loop must start at i = 1. If it starts at i = 0, the first iteration computes Math.max(nums[0], nums[0] + nums[0]), double-counting the first element — on [5] you'd get 10.nums = [], nums[0] is undefined, and Math.max(undefined, ...) is NaN — which then poisons every later comparison. Guard nums.length === 0 up front and return your documented value (0 here). Decide the policy once and pin it with a test; don't let it fall through to NaN.bestEndingHere as the return value. It holds the best run ending at the last element, not the best overall. On [5, -100, 1] it ends at 1, but the answer is 5. Always return bestSoFar.let best = nums[0] then comparing best + x without the reset. If you only ever do best = Math.max(best, best + x) you never allow a fresh start, so one early catastrophic loss caps every later run forever. The Math.max(x, ...) branch is what lets the algorithm recover after a dip.x > bestEndingHere + x), the run now begins at i. Whenever bestSoFar improves, record the current run's [start, i] as the best bounds. You return both the sum and the slice, at no change to the O(n) cost.(top, bottom) row pairs gives O(rows² × cols).max(normal Kadane max, totalSum − Kadane minimum-subarray) — the wrap-around best is the total minus the worst middle stretch you exclude. Watch the all-negative edge case: if every element is negative, the second term is wrong (it would pick the empty run), so fall back to the plain Kadane maximum.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
You're looking at a row of daily profit-and-loss numbers for a trading desk: some days you gained, some days you lost. You want the single best streak — a run of consecutive days whose net total is the highest possible. You can't skip a bad day in the middle and stitch two good runs together; the run has to be unbroken. Given an array of numbers (positive, negative, or zero), arrayMaximumSumContiguous(nums) returns the largest sum obtainable from any contiguous, non-empty slice of that array. This is the classic maximum subarray problem, solved optimally by Kadane's algorithm.
function arrayMaximumSumContiguous(nums: number[]): number;
// returns the largest sum of any contiguous, non-empty subarray.
// the subarray must be a single unbroken run — no skipping elements.// A mix of gains and losses. The best run is [4, -1, 2, 1], summing to 6.
// Taking the 4 alone gives only 4; dipping through -1 to reach 2 and 1 pays off,
// but the -5 just after is too costly to cross to reach the trailing 4.
arrayMaximumSumContiguous([-2, 1, -3, 4, -1, 2, 1, -5, 4]); // 6// Every number is negative. There's no way to reach a positive sum, and an
// empty run isn't allowed — so the answer is the single least-bad element, -1.
arrayMaximumSumContiguous([-8, -3, -6, -1, -7]); // -1[1, 3] from [1, 2, 3] is not contiguous; [1, 2] and [2, 3] are.[-8, -3, -1] the answer is -1, never 0.0. When nums is [], there is no element to pick; this implementation defines the answer as 0. (Some variants throw instead — we pick 0 here and the tests pin it down. If your contract differs, change this one line and its test.)[5] is 5; [-5] is -5.You'll find the largest sum reachable from any single unbroken run of an array, in one pass, by tracking just two running numbers.
You have a row of numbers — think of them as daily profits and losses on a trading desk. Some days you gain, some you lose. You want the single best streak: a run of consecutive days whose net total is as high as it can be. You're not allowed to cherry-pick the good days and drop the bad ones from the middle — the run has to be one continuous stretch. So the question becomes: where do you start the run, and where do you stop, to walk away with the most?
The slippery parts are the negatives. A losing day inside a great streak might still be worth crossing if the days around it more than make up for it. But a huge loss in the middle can be bad enough that nothing on the far side is worth reaching back across — at that point you're better off forgetting the past and starting a fresh run. Knowing when to carry a bad day forward and when to cut your losses is the whole problem.
Here's the array we'll keep coming back to: [-2, 1, -3, 4, -1, 2, 1, -5, 4]. The best contiguous run is [4, -1, 2, 1], which totals 6. Notice it includes a negative (-1) — crossing that loss was worth it because 4 before it and 2 + 1 after it more than paid for it. But the run stops before the -5: that loss is too steep, and the lone 4 at the end can't claw it back.
The key insight that unlocks the fast solution: as you scan left to right, the only question that matters at each element is "what's the best run that ends right here?" If you know that for every position, the overall answer is just the largest of those per-position bests. And the best run ending at position i has only two shapes: either it's just the element nums[i] standing alone, or it's nums[i] glued onto the best run ending at i - 1. You pick whichever is larger.
The obvious approach mirrors the problem statement directly: a run is defined by where it starts and where it ends, so try every (start, end) pair, add up the elements between them, and keep the biggest total.
function maxSubarrayBrute(nums) {
if (nums.length === 0) return 0;
let best = -Infinity;
for (let start = 0; start < nums.length; start++) {
let sum = 0;
for (let end = start; end < nums.length; end++) {
sum += nums[end]; // extend the run one element to the right
if (sum > best) best = sum; // every (start, end) is a candidate
}
}
return best;
}This is correct. Seeding best with -Infinity (not 0) is what makes it return the largest single element on an all-negative array instead of a bogus 0 — every real sum beats -Infinity, so the closest-to-zero element wins. The inner loop reuses its running sum rather than re-adding from scratch, so it's O(n²), not O(n³). But O(n²) still means that for an array of 10,000 numbers you're doing roughly 50 million additions — and you're recomputing overlapping sums you've already seen. There's structure here we're throwing away.
The structure we threw away: when you slide the run's end one step to the right, the best run ending at the new position is almost entirely determined by the best run ending at the previous position. You don't need to re-examine every possible start. This is Kadane's algorithm.
function arrayMaximumSumContiguous(nums) {
// Documented contract: an empty array has no element to pick, so we
// define its answer as 0. (Swap this for `throw` if your spec differs.)
if (nums.length === 0) return 0;
// Seed BOTH trackers with the first element, not 0. The run must be
// non-empty, so the smallest possible answer is a single element —
// seeding with 0 would wrongly let an all-negative array return 0.
let bestEndingHere = nums[0]; // best run that must end at the current index
let bestSoFar = nums[0]; // best run seen anywhere so far
for (let i = 1; i < nums.length; i++) {
const x = nums[i];
// Either start fresh at x, or extend the previous run by x —
// whichever is larger. This single line is the reset decision.
bestEndingHere = Math.max(x, bestEndingHere + x);
// The global answer is the best ending-here we've ever seen.
bestSoFar = Math.max(bestSoFar, bestEndingHere);
}
return bestSoFar;
}
module.exports = { arrayMaximumSumContiguous };Two variables, one pass, O(n) time and O(1) extra space. The shift from the naive version is the line bestEndingHere = Math.max(x, bestEndingHere + x). Read it as a fork in the road at every element: is the run I've been building still helping me? If bestEndingHere is positive, carrying it forward (bestEndingHere + x) beats starting over, so you extend. If it's negative, it's a debt — x alone is bigger than x plus a negative — so you abandon the old run and reset to just x. You never have to look back at where the run started; the previous bestEndingHere already summarises everything to the left that's worth keeping.
Why two variables and not one? bestEndingHere is local and volatile — it rises and falls and resets as the scan moves. bestSoFar is a high-water mark that only ever goes up. If you tried to return bestEndingHere, you'd report the best run ending at the last element, which is usually not the best run overall. You have to snapshot the peak as you pass it, because the scan will keep moving and may reset right after the best run ends.
Let's trace a small array built to show the reset: [3, -1, 4, -10, 2]. The best run is the front [3, -1, 4] = 6; the -10 is a wall that resets everything after it.
init bestEndingHere = 3, bestSoFar = 3 (both seeded with nums[0])
i=1, x=-1 max(-1, 3 + -1) = max(-1, 2) = 2 → extend (carry was positive)
bestEndingHere = 2, bestSoFar = max(3, 2) = 3
i=2, x=4 max(4, 2 + 4) = max(4, 6) = 6 → extend
bestEndingHere = 6, bestSoFar = max(3, 6) = 6 ← new peak
i=3, x=-10 max(-10, 6 + -10) = max(-10, -4) = -4 → carry (both are awful,
bestEndingHere = -4, bestSoFar = max(6, -4) = 6 -4 still beats -10)
i=4, x=2 max(2, -4 + 2) = max(2, -2) = 2 → RESET (carrying the -4 debt
bestEndingHere = 2, bestSoFar = max(6, 2) = 6 is worse than 2 alone)
return 6
The decisive moment is i=4. The running sum had gone underwater to -4 after the -10. When x = 2 arrives, bestEndingHere + x is -2, but x alone is 2. Kadane takes the larger — it resets, throwing away the -10 and everything before it, because no run that has to drag the -10 along can ever be the winner. Meanwhile bestSoFar never dropped: it locked in 6 back at i=2 and held it. That's exactly why you need the second variable.
0 on an all-negative array. This is the single most common bug. It happens when you seed bestSoFar = 0 (or write Math.max(0, ...) anywhere). On [-3, -1, -2] the true answer is -1, the least-bad single element — but a 0 seed reports 0, a sum no non-empty run can actually produce. Seed with nums[0] instead, so the trackers start from a real element.bestEndingHere to 0 instead of Math.max(x, bestEndingHere + x). A popular but broken variant does bestEndingHere = Math.max(0, bestEndingHere + x) to "drop negative runs." That secretly assumes the empty run (sum 0) is allowed, so it also returns 0 on all-negative input. The correct reset floor is x itself, never 0 — the run must always contain at least the current element.i = 0. Because you seed both trackers with nums[0], the loop must start at i = 1. If it starts at i = 0, the first iteration computes Math.max(nums[0], nums[0] + nums[0]), double-counting the first element — on [5] you'd get 10.nums = [], nums[0] is undefined, and Math.max(undefined, ...) is NaN — which then poisons every later comparison. Guard nums.length === 0 up front and return your documented value (0 here). Decide the policy once and pin it with a test; don't let it fall through to NaN.bestEndingHere as the return value. It holds the best run ending at the last element, not the best overall. On [5, -100, 1] it ends at 1, but the answer is 5. Always return bestSoFar.let best = nums[0] then comparing best + x without the reset. If you only ever do best = Math.max(best, best + x) you never allow a fresh start, so one early catastrophic loss caps every later run forever. The Math.max(x, ...) branch is what lets the algorithm recover after a dip.x > bestEndingHere + x), the run now begins at i. Whenever bestSoFar improves, record the current run's [start, i] as the best bounds. You return both the sum and the slice, at no change to the O(n) cost.(top, bottom) row pairs gives O(rows² × cols).max(normal Kadane max, totalSum − Kadane minimum-subarray) — the wrap-around best is the total minus the worst middle stretch you exclude. Watch the all-negative edge case: if every element is negative, the second term is wrong (it would pick the empty run), so fall back to the plain Kadane maximum.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.