Day 25/75: Maximum Subarray Sum With Kadane's Algorithm

75 Day DSA in Java Challenge

I had an int[] of one company's daily profit and loss, one value per trading day, plenty of them negative. The report needed the best contiguous stretch: the run of consecutive days whose profit summed to the largest total. This is LeetCode 53, Maximum Subarray, dressed up in a real task.

The brute force that timed out

My first solution tried every window. Pick a start, walk every end, sum the days between, keep the largest total.

static int maxSumBrute(int[] a) { int best = Integer.MIN_VALUE; for (int start = 0; start < a.length; start++) { int sum = 0; for (int end = start; end < a.length; end++) { sum += a[end]; best = Math.max(best, sum); } } return best; // O(n^2): every window summed from scratch } 

Correct, and instant on a single year of ~250 days. Then the same report ran across a 4,000-symbol universe on every refresh. The nested loops are O(n^2) per array, and across thousands of arrays the refresh timed out.

Where the time actually went

The inner loop is the problem. With start fixed at 0, I sum the window [0..end] for every end. Then start moves to 1 and I recompute nearly the same sums again. Consecutive starts overlap massively, and I reused none of that work. Every window was summed from scratch.

So the real question is not "check all windows faster." It is: what single value can I carry forward so I never re-sum a range? That value is the best-sum window ending at the current day.

Kadane: one running value, one decision per day

Walk left to right holding maxEndingHere, the largest sum of any window ending exactly at the current index. Each day there is one choice: extend yesterday's window by adding today's value, or start a fresh window at today. Keep whichever is larger.

static int kadane(int[] a) { int maxEndingHere = a[0]; int maxSoFar = a[0]; for (int i = 1; i < a.length; i++) { maxEndingHere = Math.max(a[i], maxEndingHere + a[i]); maxSoFar = Math.max(maxSoFar, maxEndingHere); } return maxSoFar; // O(n), one pass } 

A second variable, maxSoFar, records the best window seen anywhere, because the optimal window ends on some day and maxEndingHere is the best window ending on each one.

Why "reset when negative" is the same rule

If the window ending yesterday summed to something negative, carrying it into today only lowers today's value -- a positive plus a negative is smaller than the positive alone. So the instant maxEndingHere + a[i] loses to a[i] on its own, the past is a liability and you drop it. A negative running prefix never helps anything downstream. That is exactly the "reset the running total when it goes negative" phrasing you will see elsewhere, just expressed as a Math.max.

The base case that bit me

My first attempt seeded both variables at 0 and looped from index 0. It passed everything until an all-negative array such as {-8, -3, -6, -2}, where the correct answer is -2 (the least-bad single day) because the window must be non-empty. A zero seed reports 0, an empty window, which is wrong here. Seed both with the first element and loop from index 1:

• int best = a[0]; int endingHere = a[0];
• for (int i = 1; i < a.length; i++)

If your variant is allowed to return 0 for an empty window, that is a different problem with a different base case. The two are easy to confuse because most random inputs contain a positive number that never exposes the bug.

Recovering the actual window, not just the sum

The brute force gave me the bounds for free; Kadane needs a little bookkeeping. Track a tentative start that jumps to the current index on every reset, plus bestStart/bestEnd that you snapshot whenever maxEndingHere beats maxSoFar.

static int[] maxSubarrayWithBounds(int[] a) { int maxEndingHere = a[0], maxSoFar = a[0]; int start = 0, bestStart = 0, bestEnd = 0; for (int i = 1; i < a.length; i++) { if (a[i] > maxEndingHere + a[i]) { maxEndingHere = a[i]; start = i; // reset the window's left edge } else { maxEndingHere = maxEndingHere + a[i]; } if (maxEndingHere > maxSoFar) { maxSoFar = maxEndingHere; bestStart = start; bestEnd = i; } } return new int[]{maxSoFar, bestStart, bestEnd}; } 

Same single pass, same O(n), three extra integers. For the report I needed the dates, so this is the version that shipped.

Takeaway

The brute force was not buggy -- it answered "best contiguous-sum window" perfectly. It just could not do it cheaply, because it treated every window as unrelated to the one before it. Kadane's insight is that the best window ending today is one comparison from the best window ending yesterday: extend it, or reset it the moment the running sum turns negative. Seed on the first element so the empty window cannot sneak in, and O(n^2) collapses to a single O(n) sweep.