maximum-subarray

Difficulty: Easy  ·  Topic: 1-D Dynamic Programming  ·  Practice it on parikshan: /practice/maximum-subarray/start

The story

Uber Eats Pricing runs a continuous experiment: every minute, the demand-surge model emits a signed delta to a baseline price for one city. Some minutes the delta is positive (peak hour, push the price up); some minutes it is negative (a quiet pocket, push it down). The product team wants the single contiguous window of minutes during which the running sum of deltas was largest. That window will be the bucket they shadow-test next week.

That window is maximum-subarray. Once you see it framed this way, the same problem appears across the enterprise: profit windows on a stock ticker, biggest gain in a streaming click-through rate experiment, longest hot streak in a server's request latency, peak-to-trough window in a forecast residual.

What's actually being asked

Given an integer array nums of length n, find a contiguous non-empty subarray with the largest sum and return that sum.

A contiguous subarray is a slice nums[i..j] with 0 <= i <= j < n. You must pick at least one element.

Examples:

• nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] → 6. The window [4, -1, 2, 1] sums to 6.
• nums = [5] → 5.
• nums = [-3, -1, -4, -1, -5] → -1. All values negative; pick the least bad single element.

The naive approach

Try every (i, j) pair:

def max_sub(nums):
    n = len(nums)
    best = nums[0]
    for i in range(n):
        for j in range(i, n):
            s = sum(nums[i:j+1])
            if s > best: best = s
    return best

O(n³) with the inner sum. Even with prefix sums (O(n²)), at n = 10⁵ you are looking at 10¹⁰ operations. TLE.

The key insight

For each ending index i, ask: "what is the largest sum of any subarray that ends at i?" Call that cur. There are only two candidates: the best subarray ending at i-1 extended by nums[i], or a fresh subarray starting at i itself. So:

# Kadane's recurrence (DP collapsed to one variable):
# cur[i] = max( nums[i] , cur[i-1] + nums[i] )
# best   = max over i of cur[i]
#
# Equivalently: if cur[i-1] < 0, restart at nums[i].
# Otherwise extend.

This is the simplest DP that exists: state is one scalar, transition is one max. The answer is the running max of cur over the scan.

The four DP questions:

1. State: cur[i] is the maximum sum of any subarray that ends exactly at index i.
2. Base case: cur[0] = nums[0].
3. Transition: cur[i] = max(nums[i], cur[i-1] + nums[i]).
4. Answer: max(cur[i] for i in 0..n-1).

Step-by-step approach

Bottom-up, with array:

def kadane(nums):
    n = len(nums)
    cur = [0] * n
    cur[0] = nums[0]
    best = cur[0]
    for i in range(1, n):
        cur[i] = max(nums[i], cur[i-1] + nums[i])
        if cur[i] > best: best = cur[i]
    return best

The array is silly because cur[i] only ever reads cur[i-1]. Collapse to one scalar (this is what every textbook calls "Kadane's algorithm"):

def kadane(nums):
    cur = best = nums[0]
    for i in range(1, len(nums)):
        cur = max(nums[i], cur + nums[i])
        if cur > best: best = cur
    return best

O(n) time, O(1) space.

Worked example

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

Return 6. Verified.

Complexity

• Time: O(n) single pass.
• Space: O(1) with two scalars.

Compare to brute force: O(n²) at best (with prefix sums) or O(n³) naive. The single-variable DP is the cleanest possible specimen of the DP family: the entire DP table collapses to one number because the recurrence reads only the immediately preceding cell.

Common pitfalls

• Initialising best = 0 instead of nums[0]: fails on all-negative arrays. The empty subarray sums to 0, but the spec forbids empty subarrays.
• Inner loop allocates: writing cur = max(nums[i], sum(window)) accidentally turns O(n) into O(n²). Trust the recurrence.
• Off-by-one on the loop start: range(1, n), not range(n), because cur is already initialised to nums[0].
• Confusing "subarray" with "subsequence": subarray means contiguous; subsequence means any order-preserving selection. They are different problems entirely; do not mix them up.

Where this shows up in the enterprise

• Uber pricing optimisation: longest contiguous window of positive surge delta. Decide where to A/B test the next experimental price.
• Stripe revenue analytics: find the consecutive hours of highest merchant revenue increment after a feature launch.
• Bloomberg trading analytics: longest positive PnL window for a strategy. Drives risk-on / risk-off decisions.
• Netflix recommender quality: find the contiguous block of episodes where viewer retention delta was strongest.
• PagerDuty incident analytics: longest stretch of clean (negative) anomaly score after a remediation.
• Speech recognition (Apple Siri, Google Assistant): when scoring acoustic features against a noise baseline, the contiguous high-confidence stretch is the candidate utterance.
• Genomics (Illumina, Oxford Nanopore): scan a per-base quality-score delta to find the longest contiguous high-quality read span; trim everything else.
• NLP sentiment (HuggingFace transformer outputs): scan per-token sentiment score; find the most polar contiguous span.

Wherever a series of signed deltas streams in and you want "where was the action concentrated", this is your tool.

Variants you'll see elsewhere

• maximum-product-subarray: replace addition with multiplication. The DP needs two scalars because sign matters; see the next article in this cluster.
• circular-subarray-sum: the array wraps around; trick is total - min_subarray for the wrap case.
• best-time-to-buy-and-sell-stock: rephrase as Kadane over price deltas; one buy, one sell.
• maximum-sum-rectangle-in-2d-matrix: enumerate row pairs, collapse to columns, run Kadane on the column sums. Classic application.
• longest-turbulent-subarray: same DP shape, different per-step compatibility check.

How parikshan turns this into a learning loop

Kadane is one of the highest-leverage 20 lines of code in the whole canon. Drill it.

1. Read this article. The recurrence collapses the DP table to one number; this is the canonical "rolling state" example.
2. Practice mode with no AI: write Kadane in five minutes flat. If you cannot, write the array version first and watch the array reduce to one variable as you stare at the loop.
3. AI training: Explain the recurrence. The assistant should reproduce "cur ends at i; either restart or extend". If it says "track a running sum and reset to 0 when negative" you are getting a slight simplification; both produce the same answer on positive-and-mixed inputs, but the simplification fails on all-negative arrays.
4. Exam mode with the proctor on. The bank's adversarial private test on maximum-subarray includes [-3, -1, -4, -1, -5] (all negative). If you initialised best = 0, you will fail. Use the dispute flow only if you believe the failure is a judge bug; here it is your bug.
5. Stack the cluster: chain into maximum-product-subarray next. The pivot from one scalar (sum) to two scalars (max and min product) is the most common interview trick built atop Kadane.

In the AI-integrated workspace

Kadane is short enough that AI agents almost always write it correctly. The failure modes shift accordingly.

• The all-negative bug is the single most common AI mistake on this problem. An agent writes cur = max(0, cur + nums[i]) (clip at zero) and then reports max(cur). On [-3, -1] this returns 0, not -1. The fix is cur = max(nums[i], cur + nums[i]).
• The empty-array crash: agents often forget n == 0 (though this spec forbids it). Worth a defensive check in production code, not in interviews.
• The off-by-one on the start: agents write for i in range(n) and initialise cur = 0, breaking the all-negative case again.

The 2027 engineer's discipline:

1. Recognise Kadane. The spec says "contiguous", "maximum sum", "subarray": that is Kadane, every time. Recognition in two seconds is the entire skill.
2. Verify on [-1] and [-3, -1, -4] before shipping. Every Kadane implementation should return -1 and -1 on these two inputs respectively. If it returns 0, the implementation is wrong.
3. Demand O(1) space. The array version is a smell; the one-scalar form is the only acceptable production code.
4. For the 2-D matrix variant (frequent in interviews), instruct the agent to "enumerate the top and bottom row, collapse columns to a 1-D array, run Kadane". That single sentence directs the agent to the right algorithm; without it, the agent often produces an O(n⁴) brute force.