A clearing house posts signed settlement deltas every minute. Finance wants the hottest consecutive stretch — the window they would have wanted to keep open. The intern nested every start and end, adding a[i] through a[j]. A day of minutes returned. A quarter of minutes was still looping when the board pack was due.

Maximum Subarray asks for the largest sum of a contiguous slice. An array already gives a[i] for free. Nested i..j uses that and still pays O(n²). This is not a subsequence: you may drop a prefix, never punch a hole in the middle.

This is an interview writeup, not a named-algorithm lecture. The Kadane post owns the recurrence, the empty-vs-nonempty spec, and recovering indices. Here we only care about one decision per index: extend the run that already ends here, or start over at this value.

The problem

Given a non-empty int[] nums, return the largest sum of any contiguous subarray. The subarray must contain at least one element. Order of values is the layout you are given; you may not skip an index inside the chosen slice.

nums = [-3, 2, -1, 5, -4]  →  6    slice [2, -1, 5]
nums = [4, -1, 3]          →  6    the whole array
nums = [-7, -2, -5]        → -2    the least-negative singleton

Note: A subsequence could skip the -1 between 2 and 5. This prompt forbids holes. If they allow an empty slice with sum 0, all-negative input would answer 0 — that is a different spec. Interview wording that says “contiguous subarray” without mentioning empty almost always means non-empty.

Nested slices are the honest brute force

Every pair of endpoints is a candidate. Keep a running total from i so you do not re-sum the inner range. Correct. Quadratic.

int maxSubarrayNested(int[] nums) {
    int best = Integer.MIN_VALUE;
    for (int i = 0; i < nums.length; i++) {
        int sum = 0;
        for (int j = i; j < nums.length; j++) {
            sum += nums[j];
            best = Math.max(best, sum);
        }
    }
    return best;
}

Prefix sums make each i..j a subtraction after one precompute. That is still every pair, still O(n²). At n = 20 this is a rounding error. At n in the tens of thousands you paid nested endpoints for a question one running ending-sum answers in a single pass: extend this run, or start over at this index?

One pass: best ending here, best seen so far

Walk left to right. Two running values:

  • bestEndingHere — the best contiguous sum among slices that end at this index. That is max(x, bestEndingHere + x).
  • bestSoFar — the global max of those endings. After the last index, that is the answer.

If the prefix that ends at i - 1 is already negative, adding it makes x worse. Starting fresh at i is then the only legal move that still ends here. You are not skipping a middle element — you are refusing to drag a losing prefix into the new end.

nums = [-3, 2, -1, 5, -4]

i  x    x vs prev+x     bestEndingHere   bestSoFar
0  -3   start           -3               -3
1   2   2  >  -3+2      2                2     reset at 2
2  -1   1  >  -1        1                2
3   5   6  >   5        6                6     slice [2, -1, 5]
4  -4   2  >  -4        2                6

bestSoFar = 6

At i = 1 the previous ending is -3. Extending yields -1; starting at 2 yields 2. Reset. The later -1 is kept because 2 + -1 still beats starting over, and 5 then extends that run to 6. That is the contiguous contract.

The Java is that walk. Initialize both scalars from nums[0] so an all-negative array is legal:

int maxSubarray(int[] nums) {
    int bestEndingHere = nums[0];
    int bestSoFar = nums[0];
    for (int i = 1; i < nums.length; i++) {
        int x = nums[i];
        bestEndingHere = Math.max(x, bestEndingHere + x);
        bestSoFar = Math.max(bestSoFar, bestEndingHere);
    }
    return bestSoFar;
}

Time is O(n) — one pass, constant work per index. Space is O(1) besides the two running integers. The Kadane post is the procedure; this board only needs the two scalars.

Note: Do not initialize bestSoFar to 0. Zero is the empty-slice answer smuggled into the non-empty spec. On [-7, -2, -5] the answer is -2, not 0. Clamp bestEndingHere to 0 inside the loop and you have changed the problem.

What interviewers usually poke next

  • Return the bounds, not only the sum. Track the candidate start of the current ending run, and commit start/end when bestSoFar improves. The two-int loop does not remember days. Keep indices in the same pass; do not re-scan for a matching sum afterward.
  • All negative. Non-empty means the largest element. Initialize from nums[0]. If they allow empty with sum 0, say so — that clamp is spec, not a speed hack.
  • Empty input. The prompt promised a non-empty array. In production you would reject; at the board, ask.
  • Overflow. Sums of int deltas can wrap. If the domain is money or counters that do not fit in 32 bits, use long for both running values.
  • Maximum product. A different problem. Signs and zeros flip the recurrence; this pass does not transfer. Do not invent a URL for it.
  • Daily price deltas. If they rewrite a price series as prices[i] - prices[i - 1], this pass is the one-trade profit from Best Time to Buy and Sell Stock. Same numbers, different statement — mention it, do not re-derive the floor walk here.

You are done with this problem when you can say, out loud, why every slice is correct, why this is not a subsequence, and why a negative prefix gets dropped instead of dragged.