Generated by Codex with GPT-5

Quick facts

  • Difficulty: MEDIUM
  • Problem: Maximum Subarray
  • Main tags: Array, Divide and Conquer, Dynamic Programming

What the problem is really asking

The input is an integer array, and the task is to choose one contiguous subarray whose sum is as large as possible.

The important constraint is contiguity. This is not “pick the best numbers anywhere in the array.” Once a starting point is chosen, the subarray must be one uninterrupted block.

That detail is what makes the problem interesting: a negative number may hurt the current block, but it can still be worth keeping if the surrounding positives more than make up for it.

The natural baseline

The first idea is brute force:

  • pick every possible start index
  • extend every possible end index
  • compute the sum for each subarray
  • keep the largest one

That works, but it costs O(n^2) time even with careful bookkeeping.

There is also a classic divide-and-conquer solution that splits the array around the middle and combines:

  • the best answer entirely on the left
  • the best answer entirely on the right
  • the best answer crossing the midpoint

That approach is elegant, but it still costs O(n log n), so it is not the optimal answer.

The key insight

While scanning from left to right, only one local question matters:

for a subarray that must end at the current index, is it better to:

  • extend the best subarray ending at the previous index, or
  • throw that away and start fresh at the current value?

That is the whole problem.

If the best subarray ending one position earlier has a negative sum, carrying it forward only makes the new total worse. In that case, the current element should become the new starting point.

So the best subarray ending at position i is:

max(nums[i], nums[i] + best_subarray_ending_at_i_minus_1)

Once that value is known, the global answer is simply the largest such value seen anywhere in the scan.

This is Kadane’s algorithm.

How to derive the optimal solution

A practical derivation looks like this:

  1. Start from brute force and notice that many candidate subarrays share most of their elements.
  2. Reframe the problem from “best subarray anywhere” to “best subarray that ends here.”
  3. Notice that each position only has two realistic choices: extend the previous best ending-here sum or restart here.
  4. Track the best ending-here sum and the best overall sum in one pass.

This leads to a linear-time dynamic programming solution with constant extra space.

Best approach

Kadane’s algorithm is the right default:

  • Time: O(n)
  • Extra space: O(1)
  • Why it is optimal: each element is processed once, and only two running values are maintained

One subtle but important detail: the algorithm must start from nums[0], not from 0.

That avoids a bug on all-negative arrays. For example, for [-3, -2, -5], the correct answer is -2, not 0.

Python solution

from typing import List


def best_subarray_sum_ending_here(
    previous_best_ending_here: int,
    current_value: int,
) -> int:
    """Return the best subarray sum that must end at current_value."""
    return max(current_value, previous_best_ending_here + current_value)


def maximum_subarray_sum(numbers: List[int]) -> int:
    """Return the largest sum of any contiguous subarray."""
    if not numbers:
        raise ValueError("numbers must contain at least one value")

    best_sum_seen = numbers[0]
    best_sum_ending_here = numbers[0]

    for current_value in numbers[1:]:
        # Either extend the previous window or restart at the current index.
        best_sum_ending_here = best_subarray_sum_ending_here(
            previous_best_ending_here=best_sum_ending_here,
            current_value=current_value,
        )
        best_sum_seen = max(best_sum_seen, best_sum_ending_here)

    return best_sum_seen


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        return maximum_subarray_sum(nums)

Why this works

At every index, best_sum_ending_here stores the maximum sum of a subarray that is forced to end at that exact position.

That means no valid answer is missed:

  • every contiguous subarray ends somewhere
  • when the scan reaches that end position, the best candidate ending there has been computed
  • taking the maximum over all ending positions produces the global best answer

The interview version to remember is:

if the running subarray becomes worse than starting fresh, reset at the current value; keep a separate variable for the best answer seen anywhere.