Best Contiguous Run

Problem Statement

You're given a list of integers — think of them as a day-by-day profit-and-loss ledger, where each entry can be a gain, a loss, or zero. Find the largest possible total from any contiguous run of entries (at least one entry long). The run doesn't have to start or end at the edges of the list, and since the list can contain only negative numbers, the answer isn't allowed to be an "empty" run worth 0 — it always comes from at least one real entry.

Input Format

The input is exactly one line: the values, as space-separated integers. There is at least one value.

Output Format

Print a single integer: the maximum sum achievable by any contiguous, non-empty run of the input values.

Example Walkthrough

Take the first sample, -4 3 -7 5 2 -3 6 1 -9 2. Track "the best sum of a run ending exactly at the current position" as you scan left to right. At position 0 (-4), the only run ending here is [-4] itself, so that value is -4. At position 1 (3), extending the previous run would give -4 + 3 = -1, but starting fresh with just 3 gives 3 — starting fresh is better, so the value here is 3. At position 2 (-7), extending gives 3 + -7 = -4, versus starting fresh at -7 alone — extending is better (-4 > -7), so the value here is -4. At position 3 (5), extending gives -4 + 5 = 1, versus starting fresh at 5 — starting fresh wins, so the value is 5. From here, extending keeps winning for a while: position 4 (2) gives 5 + 2 = 7; position 5 (-3) gives 7 + -3 = 4 (still better than restarting at -3); position 6 (6) gives 4 + 6 = 10; position 7 (1) gives 10 + 1 = 11 — the best value seen at any position so far. Position 8 (-9) gives 11 + -9 = 2, and position 9 (2) gives 2 + 2 = 4. Across every position, the largest value seen was 11, at position 7 — matching the expected output, and corresponding to the run 5, 2, -3, 6, 1.

Approach

Checking every possible contiguous run directly — every pair of a start and an end position — works, but costs O(n²) time, since there are roughly n²/2 such runs in a list of length n.

A smarter approach, often called Kadane's algorithm, scans the list once while tracking a single running value: the best possible sum of a run that ends exactly at the current position. At each new position, there are only two sensible options for that run: extend the best run that ended at the previous position by adding the current value onto it, or abandon that previous run entirely and start a brand new run consisting of just the current value. Whichever of those two gives a larger sum is the best run ending at the current position — there's never a reason to consider anything in between, since any run ending here either includes the position right before it (in which case extending is exactly right) or it doesn't (in which case it must start fresh here).

As the scan moves through the list, keep a separate "best sum seen anywhere so far," updated by comparing it against the best-run-ending-here value at every position. By the time the scan reaches the end, this tracks the best sum from a run ending at any position, which is exactly the answer to the whole problem: the best contiguous run overall must end at some position, so it's guaranteed to have been captured when that particular ending position was visited.

Common Mistakes

• Resetting the running sum to 0 whenever it goes negative, instead of comparing it against starting fresh at the current value. These usually agree, but not always — if the current value itself is negative, "reset to 0" (as if an empty run were allowed) gives a run sum of 0, which isn't a valid answer for an all-negative array; the correct fallback is always a run of exactly the current single value, not an empty run.
• Never letting the run reset at all — always adding every value in, no matter how bad the running total gets. Without ever comparing "extend" against "start fresh," a long stretch of very negative numbers early in the list can drag the running sum down so far that no later positive stretch can recover it, even though a fresh start partway through would have found the true best run.
• Initializing the "best sum so far" to 0 instead of the first element. For an array that's entirely negative, starting the best-so-far at 0 makes 0 look like a valid, beatable answer, when really no contiguous run in the array can ever reach 0 — the correct initial value is the sum of the smallest possible run, a single element, typically the first one, updated properly as the scan proceeds.