Maximum Subarray

Introduction

A sequence of integers — some positive, some negative — and a single objective: find the contiguous run with the largest sum. The puzzle is famous, asked in countless on-sites, and the obvious solutions are quadratic. The interesting ones are not, and the gap between “obvious” and “optimal” is the entire reason this problem keeps appearing.

The lesson is bigger than the algorithm. Most interview optimizations make a slow approach faster. The optimization here works the other way: you don’t speed up the brute force, you ask a different question whose answer happens to be linear. That move — re-stating the question so the answer falls out — is the heart of dynamic programming, and recognizing when it applies is what this chapter trains.

In dynamic programming, the optimization isn’t faster code — it’s a sharper question.

If you’re early in dynamic-programming prep, read the chapter linearly — each approach builds on the previous. If you can already write the optimal answer in your sleep, jump to the correctness section under Approach 03 and the follow-ups table; both contain something even seasoned candidates miss.

What the interviewer is actually testing

1. Naming the obvious solution and not stopping there. A brute-force answer is correct but uninteresting. The signal is whether you spot that there’s a better way without being prompted.
2. Reasoning about subproblem structure. The breakthrough comes from re-framing the question in terms of “best subarray ending here” rather than “best subarray overall.” That re-framing is the DP move; it shows up in countless other problems.
3. Constant-space discipline. The linear-time answer fits in $O(1)$ extra memory once you notice that yesterday’s subproblem solution is the only one tomorrow needs. Spotting that collapse is a senior signal.
4. Edge cases and variations. All-negative inputs, the minimum-sum variant, the longest-positive-run variant — each is a one-line tweak. Knowing them shows you understand the move, not just memorized the code.

Problem statement

Clarifying questions — and why each one matters

A mental framework — re-frame the question

The brute-force question is “what’s the largest sum across all contiguous subarrays?”. There are $O(n^2)$ subarrays, so any approach that enumerates them is at least quadratic.

The DP move is to re-frame: “for each ending position $j$, what’s the largest sum of any subarray that ends exactly at $j$?”. There are only $n$ ending positions, and — crucially — the answer for ending position $j$ has a cheap relationship to the answer for ending position $j-1$:

Either we extend the previous run by adding $A[j]$, or the previous run wasn’t worth keeping and we start a new one at $A[j]$. The decision at each cell is binary, and the global answer is just the maximum over all the per-position values. That’s the entire algorithm.

This re-framing — replacing a “best across all $X$” question with a “best ending at each $X$” recurrence — is one of the most-reused moves in dynamic programming. It works whenever extending a partial solution is a constant-time operation given the previous value.

Discussion

#include <climits>
#include <vector>

int maxSubArray(const std::vector<int>& A) {
    const int n = static_cast<int>(A.size());
    if (n == 0) return 0;

    std::vector<int> prefix(n);
    prefix[0] = A[0];
    for (int i = 1; i < n; ++i) {
        prefix[i] = prefix[i - 1] + A[i];
    }

    int best = INT_MIN;
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            const int sum = prefix[j] - (i > 0 ? prefix[i - 1] : 0);
            if (sum > best) best = sum;
        }
    }
    return best;
}

#include <algorithm>
#include <climits>
#include <vector>

namespace {

int crossSum(const std::vector<int>& A, int lo, int mid, int hi) {
    int leftBest = INT_MIN;
    int sum = 0;
    for (int i = mid; i >= lo; --i) {
        sum += A[i];
        if (sum > leftBest) leftBest = sum;
    }

    int rightBest = INT_MIN;
    sum = 0;
    for (int i = mid + 1; i <= hi; ++i) {
        sum += A[i];
        if (sum > rightBest) rightBest = sum;
    }

    return leftBest + rightBest;
}

int solve(const std::vector<int>& A, int lo, int hi) {
    if (lo == hi) return A[lo];
    const int mid = lo + (hi - lo) / 2;
    const int leftBest = solve(A, lo, mid);
    const int rightBest = solve(A, mid + 1, hi);
    const int crossBest = crossSum(A, lo, mid, hi);
    return std::max({leftBest, rightBest, crossBest});
}

}  // namespace

int maxSubArray(const std::vector<int>& A) {
    if (A.empty()) return 0;
    return solve(A, 0, static_cast<int>(A.size()) - 1);
}

#include <algorithm>
#include <vector>

int maxSubArray(const std::vector<int>& A) {
    if (A.empty()) return 0;
    int best = A[0];
    int endingHere = A[0];
    for (std::size_t i = 1; i < A.size(); ++i) {
        endingHere = std::max(A[i], endingHere + A[i]);
        best = std::max(best, endingHere);
    }
    return best;
}

Approach comparison

Default answer: Kadane. State the recurrence — “best ending here is either A[i] alone or A[i] plus best ending at i−1” — and the algorithm writes itself.

Follow-ups to anticipate

Pattern recognition — DP on running state

The move this problem teaches — re-frame a “best across all $X$” question as a recurrence over per-position best values — is a recurring shape in dynamic programming:

• House Robber. “Best loot ending at house $i$, given you can’t rob adjacent houses.” One-line recurrence: $f(i) = \max(f(i-1), f(i-2) + \text{nums}[i])$.
• Best Time to Buy/Sell Stock. Track the running minimum price; the best profit ending at day $i$ is prices[i] − runningMin. Same shape.
• Longest Increasing Subsequence. “Length of the longest LIS ending at $i$, considering all earlier positions $j$ with $A[j] < A[i]$.” Same per-position re-framing; the inner scan over earlier positions makes it $O(n^2)$ (or $O(n \log n)$ with a binary-searched tails array).
• Maximum Sum Increasing Subsequence. Hybrid of LIS and this problem; the recurrence considers all valid predecessors.
• Edit Distance. “Best alignment ending at the suffix pair $(i, j)$.” Two-dimensional but the same per-position re-framing.

The reflex: when a problem asks for the best across $O(n^k)$ structures, ask whether you can re-frame it as the best ending at each of $n$ positions. If yes, the algorithm is at most $O(n)$ per position — and the resulting algorithm is almost always exactly $O(n)$ overall.

What to say out loud — the delivery script

Ten beats:

1. “Let me restate: given an array of integers, find the contiguous subarray with the largest sum.”
2. Ask: “can A contain negatives? is the subarray required to be non-empty? sum or indices?”
3. “Brute force enumerates every $(i, j)$ pair and sums each subarray — $O(n^3)$ naïvely, $O(n^2)$ with prefix sums. Let me name that and look for something better.”
4. “There’s a divide-and-conquer angle that gets us to $O(n \log n)$ — but the linear-time answer is what most interviewers expect.”
5. “Re-frame the question: instead of ‘best subarray of the whole array,’ ask ‘best subarray ending at each index.’ That’s $n$ subproblems, each with a one-line recurrence.”
6. “At index $i$: either start fresh at $A[i]$, or extend the best subarray ending at $i - 1$. Pick whichever is larger.”
7. Write the code — five lines plus the loop. “endingHere = max(A[i], endingHere + A[i]). best = max(best, endingHere). Initialize both to $A[0]$ — that’s what makes all-negative inputs work.”
8. Trace one or two key transitions. Pick a cell where extending wins narrowly, or where restarting reverses the trend.
9. “Complexity: $O(n)$ time, $O(1)$ space. The recurrence only ever needs the previous cell’s value, so the auxiliary array collapses to a single variable.”
10. “Variations: minimum subarray flips both max calls to min. Circular subarray needs two passes. Returning indices needs two extra trackers. The core recurrence is the same.”

Summary

The largest-sum subarray problem is the rite of passage for dynamic programming. The interview signal isn’t producing the linear-time answer — it’s articulating the re-framing that makes it possible, and recognizing that the per-position recurrence collapses to a single variable.

The wider lesson is the shape of the optimization. Many interview problems ask for the best across an exponential or quadratic space of structures; many of those problems collapse to a linear-time recurrence the moment you ask the question per position rather than across all structures. House Robber, Best Time to Buy/Sell Stock, the longest-positive-run variant, the minimum-sum variant — they all yield to the same move. Internalize it here; the rest of the DP family becomes substantially less intimidating.