Maximum Subarray

Find the largest sum of a nonempty continuous subarray.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Maximum Subarray: At each index, keep the best sum ending exactly there by either extending the prior range or restarting at the current value.

Input and goalFind the largest sum of a nonempty continuous subarray.

Initialize at index 0The only nonempty subarray ending at -2 is [-2], so current=-2 and best=-2.

current startscan-2011-3243-142516-5748

currentRange[0..0]arithmeticcurrent = best = -2

Recognize it

Use this recurrence when optimizing a nonempty contiguous subarray and extending a negative accumulated prefix can only hurt every future range.

Keep true

After processing index i, current is the maximum sum of any nonempty subarray ending exactly at i, while best is the maximum sum of any subarray contained in indices 0 through i.

Reuse it

For contiguous optimization, define the best solution forced to end at the current position, decide extend versus restart, and separately preserve the best endpoint seen anywhere.

Pattern: One-dimensional DP, also called Kadane’s algorithm.

Simple idea: At each value, choose whether to start a new subarray or extend the current one. A negative earlier total is not worth carrying forward.

def max_subarray(nums: list[int]) -> int:
   current = best = nums[0]
   for num in nums[1:]:
      current = max(num, current + num)
      best = max(best, current)
   return best

Cost: $O(n)$ time and $O(1)$ space.