How to find the best streak in a single pass

Here are eight days of a trader's gains and losses:

+3   -4   +5   -1   +6   -8   +4   +2

One question: if you could rewind and pick any single unbroken stretch of days to have been in the market — start on one day, sell on a later one — which stretch would have made you the most money?

Your eye can squint at it and guess. A computer can't squint, so the obvious move is to try every stretch: every start, every end, add up the days between, keep the best. For eight days that's nothing. For a million days of tick data, it's about half a trillion additions — and you're not finishing today.

Here's the surprising part. You can find the single best stretch by walking through the days exactly once — glancing at each day for a fraction of a second, never going back — and the answer that falls out is provably the best one. You never search through the stretches at all.

The whole thing rests on one idea. Once it clicks, you'll reach for it for the rest of your life. Let's earn it.

The honest brute force

The first idea everyone has is to try every stretch — fix a start, fix an end, sum what's between, remember the best:

// the honest first attempt
let best = -Infinity;
for (let start = 0; start < n; start++)
  for (let end = start; end < n; end++) {
    let sum = 0;
    for (let k = start; k <= end; k++) sum += a[k];
    best = Math.max(best, sum);
  }

It's correct. It's also doing roughly n³ work, and even after the obvious cleanup it's n². On a million numbers that's hundreds of billions of operations. So we go hunting for the waste — and there's a mountain of it. When we sum the stretch from day 2 to day 7, we redo nearly all the addition we just did for day 2 to day 6. We keep recomputing sums we've basically already seen.

That points at a smaller, sneakier question. Instead of "what's the best stretch anywhere?", ask:

For each day, what's the best stretch that ends exactly on that day?

Because if you knew the best stretch ending on every day, the overall answer is just the biggest of those. And here's the magic: the best stretch ending today is almost free if you know the best stretch ending yesterday. A stretch ending today is only ever one of two things:

• yesterday's best stretch, with today added on, or
• today, standing completely alone, a fresh start.

That's the entire decision space. Two options. So at each day you ask yourself one question:

Is the run I've been building still pulling its weight — or is it dead weight I should drop?

If the running total you're carrying has slipped negative, it can only drag today down. Whatever good days were in it, the bad ones have already outweighed them — so the smartest move is to drop the whole thing and start fresh from today. If the running total is still positive, it's still helping: carry it forward and add today on.

Make that one decision, once per day, and you're done. That is the whole algorithm — it's called Kadane's algorithm, and the story goes that Jay Kadane produced it in under a minute when a colleague described the problem to him. Once you've seen the idea, you understand why it didn't take long.

Watch the run decide

Step through the eight days. Watch two things at once: the current run (indigo) growing or snapping back to a single day, and the best stretch so far (gold) sitting still until something finally beats it.

Two moments are worth pausing on. First, the reset at day 2: the run dragged in from the −4 had gone negative, so it gets thrown away and the window restarts fresh. Second — and this is the one that surprises people — the winning stretch ends up including day 3's −1. The best run isn't the one with no bad days. It's the one whose good outweighs its bad. A losing day in the middle of two big winners is worth keeping.

The whole thing, in five lines

Now the code — and every line is a decision you just watched happen:

function maxSubarray(a) {
let run  = a[0];   // best stretch ENDING right here
let best = a[0];   // best stretch we've seen ANYWHERE

for (let i = 1; i < a.length; i++) {
  // carry the run forward, OR drop it and start fresh at today:
  run  = Math.max(a[i], run + a[i]);
  best = Math.max(best, run);
}
return best;
}

console.log(maxSubarray([3, -4, 5, -1, 6, -8, 4, 2])); // 10  ->  [5, -1, 6]

run + a[i] is carry the streak forward; a[i] alone is start fresh. Math.max picks whichever is larger — that single comparison is the "drop the dead weight" decision. best just remembers the high-water mark as the run rises and falls. One pass, O(n) time, O(1) space.

(That returns the best sum. If you also need to know which days — the actual stretch — track the start index whenever you reset, and the start/end whenever you update best. Three extra lines, same single pass.)

What to take away

• When to reach for it: any "best continuous stretch / largest contiguous sum" question — max-profit windows, best run of form, longest good streak.
• Complexity: O(n) time, O(1) space. One pass, two variables.
• The #1 bug: if every number is negative, the best stretch is the least bad single day. Start best = a[0], not best = 0 — initializing to 0 silently returns 0 for an all-negative array, and it's the most common Kadane mistake there is.
• The bigger idea: "the best answer ending here is built from the best answer ending one step back." That recurrence — solve the small local version, let the global answer fall out — is the beating heart of dynamic programming. You just met DP without the scary name.

Try it yourself

Five problems, climbing. Don't peek at solutions until you've fought each one a little — the fight is where the learning lives.

The first time Kadane's clicks, it feels a little like cheating — like you skipped the work and the answer just showed up. You didn't. You asked a smaller question ("best stretch ending here") and let it quietly answer the big one. That move is the whole soul of dynamic programming, and you met it early. The next time a problem feels impossibly large, try shrinking the question instead of the data. It works more often than you'd think.