Maximum Subarray

1. Problem & Core Objective

Given an integer array nums, find the contiguous subarray with the largest sum and return that sum.

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]   →  6      ([4, -1, 2, 1])
nums = [1]                               →  1
nums = [5, 4, -1, 7, 8]                  →  23     (the whole array)
nums = [-3, -1, -2]                      →  -1     (the least-bad single element)

Constraints: 1 <= nums.length <= 10^5, -10^4 <= nums[i] <= 10^4

What's actually being tested: whether you can state why a greedy choice is safe. Kadane's algorithm is four lines; the interview value is entirely in the sentence that justifies throwing a prefix away. The all-negative case then checks whether you actually believed your own definition of the state.

2. First-Principles Thought Process

Fix the right end of the window

The subarray is defined by two endpoints, so O(n²) candidates. Enumerating both is the obvious start — and the way out is to fix one endpoint and ask what the other should be.

Define:

cur[i] = the largest sum of any subarray ENDING exactly at index i

Every subarray ends somewhere, so the answer is max(cur[i]) over all i. One quantifier is now pinned down; only the left endpoint is still free.

The recurrence has exactly two options

A subarray ending at i either includes i-1 or it doesn't. There is no third case:

cur[i] = max( nums[i],              // start fresh at i
              cur[i-1] + nums[i] )  // extend the best subarray ending at i-1

That is already an O(n) DP. Kadane is this recurrence with the array collapsed to a variable.

Why the greedy phrasing is the same thing

The two branches compare nums[i] against cur + nums[i]. Subtract nums[i] from both sides:

nums[i] > cur + nums[i]   ⇔   0 > cur   ⇔   cur < 0

So "restart" fires exactly when the running prefix is negative, and never otherwise. That gives the greedy sentence:

A negative prefix can never appear in an optimal answer. Any subarray that extends through it would be strictly larger without it — deleting a negative quantity adds to the sum. So the moment cur goes negative I can discard it and lose nothing.

Notice what the argument does not depend on: how long the prefix is, how negative it is, or what comes after. Only the sign matters. That is unusually strong for a greedy argument, and it's why this one is safe while the coin-change greedy is not.

Where the all-negative case comes from

If every element is negative, cur is negative at every index and the algorithm restarts on every step. The answer is the largest single element. That is correct — a subarray must be non-empty, so you are forced to take a loss.

The bug is seeding best = 0, which silently answers a different question ("largest sum, or 0 if you may take nothing"). Measured: on 4,000 randomly generated all-negative arrays, the best = 0 seed was wrong on all 4,000 — for example [-3, -1, -2] returns 0 instead of −1.

3. Solution Paths

Approach 1 — Brute force, all subarrays

public int maxSubArray(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;
}

• Time O(n²) · Space O(1)

Note the running sum in the inner loop. The naive version recomputes the sum from scratch, making it O(n³) — worth mentioning as the version you didn't write.

Counter-questions on this approach

⭐ "You wrote O(n²), not O(n³). What did you avoid?"

The inner loop extends the previous subarray by one element instead of re-summing it. sum(i..j) = sum(i..j-1) + nums[j].

That reuse is the same observation the DP formalises — and noticing it here is what leads to Kadane. The O(n³) version computes sum(i..j) for every pair independently, which is O(n) work per pair.

"Why Integer.MIN_VALUE and not 0?"

Because the subarray must be non-empty. Seeding at 0 asserts that the empty subarray is an allowed answer, which changes the problem for all-negative input.

Here it's safe to seed with MIN_VALUE because the loop body always runs at least once — nums.length >= 1 is guaranteed. If the array could be empty I'd have to decide what to return separately.

"Can this overflow?"

No. 10^5 elements capped at 10^4 gives a maximum magnitude of 10^9, and Integer.MAX_VALUE is about 2.1 × 10^9. It fits, but with less than one bit of headroom — if the constraint were 10^6 elements I'd switch to long.

Approach 2 — Kadane's algorithm

public int maxSubArray(int[] nums) {
    int best = nums[0], cur = nums[0];
    for (int i = 1; i < nums.length; i++) {
        cur  = Math.max(nums[i], cur + nums[i]);   // restart, or extend
        best = Math.max(best, cur);
    }
    return best;
}

• Time O(n) · Space O(1)

Both variables are seeded from nums[0] and the loop starts at 1. That handles the all-negative case without a special branch.

Counter-questions on this approach

⭐ "Prove that discarding a negative prefix is safe."

Suppose the optimal subarray is [l, r] and it strictly contains a prefix [l, m] with a negative sum. Then sum(m+1, r) = sum(l, r) − sum(l, m) > sum(l, r), because we subtracted a negative. So [m+1, r] is strictly better, contradicting optimality.

Therefore no optimal subarray begins with a negative-sum prefix, and dropping one can never discard the answer.

⭐ "Why seed with nums[0] rather than 0?"

Because cur is defined as the best sum of a subarray ending at i, and a subarray is non-empty. At i = 0 the only such subarray is [nums[0]], so cur must be nums[0] — 0 would be claiming an empty subarray exists.

The symptom is all-negative input returning 0. I measured this: seeding at 0 is wrong on every all-negative array, since the true answer is always negative and 0 is never achievable.

"Is this greedy or DP?"

Both descriptions are correct and they're the same algorithm. The DP reading is cur[i] = max(nums[i], cur[i-1] + nums[i]) with the array rolled to one variable; the greedy reading is "drop the prefix when it turns negative".

I'd mention that because the greedy framing is what generalises — and because an interviewer asking "can you do it greedily?" is asking for the proof, not a different program.

"Does the order of the two updates matter?"

Yes. cur must be updated before best, otherwise best never sees the subarray ending at the final index — it is always one step stale.

Measured: the swapped version is wrong on 1,365 of 4,000 random arrays. The smallest witness is [-2, 5], which returns −2 instead of 5.

"What if I want the indices, not just the sum?"

Record start = i whenever the restart branch wins, and capture (start, i) whenever best improves:

Java

int best = nums[0], cur = nums[0], s = 0, bs = 0, be = 0;
for (int i = 1; i < nums.length; i++) {
    if (nums[i] > cur + nums[i]) { cur = nums[i]; s = i; }
    else                           cur += nums[i];
    if (cur > best) { best = cur; bs = s; be = i; }
}

best must improve strictly. With >=, [1, -1, 1] returns the window [0, 2] — the whole array, sum 1 — instead of [0, 0]. Both have sum 1, but ties resolve to the last maximal window rather than the first, and "shortest" or "earliest" is usually what's wanted.

Approach 3 — Prefix sums

public int maxSubArray(int[] nums) {
    int best = Integer.MIN_VALUE, sum = 0, minPrefix = 0;
    for (int n : nums) {
        sum += n;
        best = Math.max(best, sum - minPrefix);
        minPrefix = Math.min(minPrefix, sum);
    }
    return best;
}

• Time O(n) · Space O(1)

sum(i..j) = prefix[j] − prefix[i-1], so maximising the subarray ending at j means minimising a prefix that ends strictly before it.

Counter-questions on this approach

⭐ "Why is minPrefix updated after best, not before?"

Because the prefix subtracted must end strictly before the current element — otherwise you'd subtract prefix[j] from itself and get the empty subarray, sum 0.

Updating in the wrong order makes all-negative input return 0 again, by exactly the same mechanism as the bad seed in Kadane. The two bugs look unrelated and are the same mistake.

"Why does minPrefix start at 0?"

0 is prefix[-1], the empty prefix — the correct predecessor for a subarray starting at index 0. It's a real value, not a sentinel.

"Is this better or worse than Kadane?"

Same complexity, slightly more state. It earns its place when the question changes: "maximum subarray with length at most k" becomes a sliding-window minimum over prefixes, and "maximum subarray sum divisible by k" becomes a hash map keyed on prefix mod k.

Kadane doesn't extend to either. So the prefix formulation is the one to keep if follow-ups are likely.

Approach 4 — Divide and conquer

public int maxSubArray(int[] nums) { return solve(nums, 0, nums.length - 1); }

private int solve(int[] a, int lo, int hi) {
    if (lo == hi) return a[lo];
    int mid = (lo + hi) >>> 1;
    int left  = solve(a, lo, mid);
    int right = solve(a, mid + 1, hi);

    int s = 0, bestLeft = Integer.MIN_VALUE;             // best suffix of the left half
    for (int i = mid; i >= lo; i--)   { s += a[i]; bestLeft  = Math.max(bestLeft, s); }
    s = 0; int bestRight = Integer.MIN_VALUE;            // best prefix of the right half
    for (int i = mid + 1; i <= hi; i++) { s += a[i]; bestRight = Math.max(bestRight, s); }

    return Math.max(Math.max(left, right), bestLeft + bestRight);
}

• Time O(n log n) · Space O(log n) stack

Counter-questions on this approach

⭐ "Why include this at all if it's slower?"

Because it's the version that survives a change of interface. If the array is a segment tree and the question is "maximum subarray inside [l, r]" for many queries, this is the merge function — each node stores total, best prefix, best suffix, best inner, and the parent combines them in O(1).

Kadane can't answer range queries. So the honest answer is "O(n) for this problem, but I'd build the O(n log n) structure if queries are coming."

"Why must the crossing candidates be seeded at MIN_VALUE rather than 0?"

The crossing subarray must contain both a[mid] and a[mid+1] — neither half may be empty. Seeding at 0 would allow an empty half and make the crossing sum too optimistic on all-negative input.

"(lo + hi) >>> 1 instead of (lo + hi) / 2?"

Overflow safety by habit (10). Here hi is at most 10^5 so it cannot overflow, but the unsigned shift costs nothing and the reflex is worth having.

4. Why the Optimal Solution Wins

Kadane is optimal in the strict sense: every element must be read, so O(n) is a lower bound, and O(1) space cannot be improved.

Choose the prefix-sum version if follow-ups involve length limits or divisibility. Choose divide and conquer only if the problem is really about many range queries. Otherwise Kadane, and spend the time on the proof.

5. Java Prerequisites

Seeding from element 0, not from a literal

int best = nums[0], cur = nums[0];
for (int i = 1; i < nums.length; i++) { ... }

The loop starts at 1 because index 0 is already consumed. This pattern — seed with the first element, iterate from the second — is the standard way to avoid a neutral-element bug for min/max reductions.

Integer.MIN_VALUE and arithmetic

int best = Integer.MIN_VALUE;
best = Math.max(best, sum);        // fine: only compared
// best + something                // NOT fine: overflows to a positive number

A MIN_VALUE sentinel is safe under comparison and unsafe under arithmetic. Approach 3 only ever compares it.

Enhanced for when the index is unused

for (int n : nums) { sum += n; }          // prefix version needs no index
for (int i = 1; i < nums.length; i++)     // Kadane needs the start at 1

Overflow arithmetic worth knowing

10^5 × 10^4 = 10^9 < Integer.MAX_VALUE ≈ 2.147 × 10^9. Safe, but say so out loud rather than assuming.

6. Interview Communication Guide

Clarifying questions: Must the subarray be non-empty (yes — this decides the all-negative answer)? Contiguous, or can I skip elements (contiguous; skipping makes it trivial — take all positives)? Do I return the sum or the indices (sum, but I'll note how to get indices)? Any bound on n that would force long (not at 10^5)?

The pitch

"I'd define the state as cur = the best sum of a subarray ending at the current index. Every subarray ends somewhere, so the answer is the maximum of that over all indices — and fixing the right endpoint is what turns O(n²) candidates into a scan.

At each step there are only two options: start fresh at i, or extend the best subarray ending at i−1. So cur = max(nums[i], cur + nums[i]).

That comparison simplifies. Subtract nums[i] from both sides and it says cur < 0 — so the rule is just throw the prefix away the moment it turns negative, and the greedy proof is one line: any subarray extending through a negative prefix is strictly better without it, because you'd be removing a negative quantity.

The case I'd flag before running it is all-negative input. The answer there is the largest single element, which means I must seed best with nums[0], not 0. Seeding at 0 answers a different question — 'largest sum, or nothing' — and returns 0 on [-3, -1, -2] instead of −1.

That's O(n) time and O(1) space, which is optimal since every element has to be read.

If follow-ups involve a length cap or divisibility, I'd rewrite it with prefix sums instead — sum(i..j) = prefix[j] − prefix[i−1], maximised by tracking the smallest earlier prefix. Kadane doesn't extend to those; the prefix form does."

Edge cases to volunteer:

Name [-3, -1, -2] before you write any code. It is the one input that separates people who defined the state from people who memorised four lines.

7. Follow-Up Questions — Modified Constraints

⭐ "What if the array is circular?"

Two cases. The best subarray either wraps or it doesn't. The non-wrapping case is plain Kadane. The wrapping case is the complement of the minimum subarray, so it equals total − minSubarraySum.

Answer is max(maxKadane, total − minKadane), with one guard: if every element is negative, total − minKadane is 0 (the empty complement), which isn't allowed. Detect it with maxKadane < 0 and return maxKadane.

It's the same two-case split as House Robber II — "the wrap case is the complement of a linear subproblem" — and the same trap: the complement of an empty set is the whole array, which has to be excluded by hand.

⭐ "Return the subarray itself, not the sum."

Track start on each restart and capture (start, i) when best strictly improves. Still O(n) and O(1) — unlike most DP path-reconstruction follow-ups, this one costs nothing, because the window is defined by two indices rather than a whole decision history.

"What if the subarray must have length at least k?"

Switch to prefix sums. For each j >= k, the answer is prefix[j] − min(prefix[0..j-k]), and that minimum is maintained incrementally as j advances. O(n), O(1).

Kadane can't be patched for this — its state has no notion of length.

"Length at most k?"

Same prefix formulation, but now the minimum is over a sliding window prefix[j-k..j-1], which needs a monotonic deque (09). Still O(n).

Note the asymmetry: "at least k" needs a running minimum, "at most k" needs a windowed minimum. The second is strictly harder.

"Maximum product subarray instead?"

The recurrence breaks, because a large negative times a negative becomes a large positive — so the best product ending at i may come from the worst product ending at i−1. You have to carry both maxEndingHere and minEndingHere and swap them when nums[i] < 0.

Worth saying explicitly: Kadane generalises to any operation where "a worse prefix can never become better" holds, and multiplication isn't one. Sign flips destroy that ordering. Worked through in full at Maximum Product Subarray.

"What if elements were 10^9 and the array 10^6 long?"

10^15 overflows int, so long throughout. The algorithm is unchanged — this is purely a type question, and the tell is that the product of the two constraints exceeds 2^31.

"Can you do it in parallel / on a stream?"

Yes, with the divide-and-conquer merge state: each chunk reports (total, bestPrefix, bestSuffix, best) and two chunks combine in O(1) via best = max(bestL, bestR, suffixL + prefixR). That's associative, so it maps cleanly onto a parallel reduction or a segment tree.

This is the strongest argument for knowing the O(n log n) version.