Maximum Subarray

Hints

1. Start with brute force. Try every (l, r) pair, sum the slice, take the max. This is O(n²) or O(n³) depending on whether you carry a running total. Get this version correct first; it's the reference for testing the optimised one.
2. Re-state the question locally. Instead of "what is the best subarray overall?", ask "for each index i, what is the best subarray ending exactly at i?" Call this f(i). The global answer is max(f(i)) across all i.
3. Find the recurrence. The best subarray ending at i either (a) extends the best subarray ending at i − 1, or (b) starts fresh at i. So f(i) = max(nums[i], f(i − 1) + nums[i]).
4. Greedy interpretation. If f(i − 1) ≥ 0, extending it can only help. If f(i − 1) < 0, starting fresh at i is strictly better. So the algorithm is: walk through the array, drop the running total whenever it goes negative.
5. Initialisation matters. Initialise both best_here and best_overall to nums[0], not 0. The subarray must be non-empty, so the answer must be at least one element. Starting at 0 silently fails on all-negative inputs.
6. Space optimisation. The recurrence only uses f(i − 1), so two scalars suffice. No DP array is needed; the algorithm runs in O(1) extra memory.

Solution: three approaches

Approach 1 · Brute force: O(n²) time, O(1) space

Iterate over every starting index; from each, extend the subarray rightward, accumulating the sum and tracking the best.

def max_subarray_brute(nums):
    n = len(nums)
    best = nums[0]
    for l in range(n):
        s = 0
        for r in range(l, n):
            s += nums[r]
            best = max(best, s)
    return best

Why it works: every contiguous subarray is enumerated exactly once. Why it's slow: there are n(n+1)/2 = Θ(n²) such subarrays. For n = 10⁵ the brute force does ~5 × 10⁹ operations, which is not viable on the upper constraint.

Approach 2 · Kadane's algorithm: O(n) time, O(1) space

The canonical solution. Walk through the array once, maintaining two scalars: the best subarray ending at the current index, and the global best seen so far.

def max_subarray(nums):
    best_here = best_overall = nums[0]
    for x in nums[1:]:
        best_here = max(x, best_here + x)
        best_overall = max(best_overall, best_here)
    return best_overall

Why max(x, best_here + x): the best subarray ending at the current index either extends the previous one (best_here + x) or starts fresh at the current element (x). The transition is forced; there are no other options.

Why initialise to nums[0]: the subarray must be non-empty. On nums = [-3, -1, -2], all sums are negative, but the answer is the largest single element. Initialising best_overall = 0 would (incorrectly) keep the initial value as the answer, which corresponds to the empty subarray, and the problem disallows that.

Why two scalars: the recurrence is f(i) = max(nums[i], f(i − 1) + nums[i]), which depends only on the previous value, not the whole history. There is no need to allocate an array of size n.

Approach 3 · Divide and conquer: O(n log n) time, O(log n) stack

Mostly an academic exercise once Kadane's exists, but worth knowing. Split the array in half. The maximum subarray either lies entirely in the left half, entirely in the right half, or crosses the midpoint. The first two cases recurse; the crossing case is computed in O(n) by extending in both directions from the midpoint.

def max_subarray_dc(nums):
    def solve(lo, hi):
        if lo == hi:
            return nums[lo]
        mid = (lo + hi) // 2
        left  = solve(lo, mid)
        right = solve(mid + 1, hi)
        # cross case: extend leftward from mid, rightward from mid+1
        s, best_left = 0, float('-inf')
        for i in range(mid, lo - 1, -1):
            s += nums[i]; best_left = max(best_left, s)
        s, best_right = 0, float('-inf')
        for i in range(mid + 1, hi + 1):
            s += nums[i]; best_right = max(best_right, s)
        return max(left, right, best_left + best_right)
    return solve(0, len(nums) - 1)

The recurrence T(n) = 2T(n/2) + O(n) resolves to O(n log n) by the master theorem, strictly worse than Kadane's for this problem. The technique earns its keep on harder problems where the cross case isn't trivially linear; for max subarray, prefer Kadane's.

Complexity comparison

Edge cases to verify

• Single element: nums = [5] → 5. The loop body doesn't execute; both scalars stay at 5.
• All negatives: nums = [-3, -1, -2] → -1. The subarray-must-be-non-empty constraint forces returning the largest single element.
• Single negative element: nums = [-5] → -5. Same logic.
• All positives: nums = [1, 2, 3] → 6. The whole array is the best subarray; best_here grows monotonically.
• Mixed with the answer at a boundary: nums = [-1, 5, -2, -3] → 5. Kadane's restarts at index 1 and immediately wins.

Where beginners go wrong

• Initialising best_overall to 0. Returns 0 on all-negative inputs, which corresponds to the empty subarray and violates the non-empty constraint. The fix is one character: initialise to nums[0].
• Resetting best_here to 0 instead of starting fresh at the current element. Subtle but wrong on all-negative inputs. The correct rule is best_here = max(x, best_here + x), not best_here = max(0, best_here + x).
• Tracking best_overall only at the end of the loop. If you update best_overall only when the loop finishes, you'll miss intermediate maxima. The update must happen every iteration.
• Trying to use sliding window or two pointers. Both techniques rely on monotonicity that doesn't hold here. Adding an element can decrease the sum (when negatives are present), and removing an element can increase it, so neither pattern's invariant survives.
• Confusing this with prefix sums plus hash map. That technique answers "subarray sums to exactly k". This one answers "what is the maximum sum?". Different questions, different tools. Kadane's is strictly simpler.

Interview follow-ups to expect

• "Return the indices, not just the sum." Track the start and end indices alongside the running total. When best_here resets to nums[i] (i.e. nums[i] > best_here + nums[i]), the start moves to i. When best_overall updates, record the current start and current i as the answer's bounds.
• "What about a circular array?" See the Kadane deep-dive: solve normally, then also solve "find the minimum subarray and subtract from total". Take the max of the two, with a guard for the all-negative case.
• "Maximum product subarray instead of sum." The recurrence breaks because negatives flip signs. Track both curr_max and curr_min; swap them when the new element is negative. Same shape, two scalars instead of one.
• "What if the array is given as a stream?" Kadane's is already streaming-friendly, it only needs the previous best_here. Process each element on arrival, in O(1) per element.
• "Generalise to maximum sum of K non-overlapping subarrays." Becomes a 2D DP where f(i, k) = best sum using k subarrays from nums[0..i]. The transition has two cases: extend the current subarray or start a new one. O(n · k) time.

Related reading

• Kadane's Algorithm: the deep-dive that explores the recurrence's geometry, the circular variant, and the product variant.
• Dynamic Programming, where Kadane's is the simplest example of an "extend or restart" DP.
• Prefix Sums in Practice: companion technique for "sum equals k" rather than "sum is maximum".