Maximum Subarray

Given an integer list nums, choose a contiguous, non-empty run of elements (a subarray) whose total is as large as possible, and return that total.

The subarray must contain at least one element, so when every value is negative the answer is the largest single value, not 0.

Example 1

Example 2

Example 3

Constraints

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

Pattern Path · Dynamic Programming · problem 147 of 169

Start simple

Try every start index and extend the end while accumulating the sum, keeping the maximum: O(n²) time, O(1) space.

The key idea

Let cur be the largest sum of a subarray that ends at the current index. When you reach a new value x, the best run ending here has only two candidates: x alone, or x appended to the best run ending at the previous index. So cur = max(x, cur + x).

Put differently, a prefix whose sum is negative is dead weight: any subarray that includes it would be larger without it, so you cut it off and restart. A prefix with a positive sum is always worth keeping.

Every subarray ends somewhere, so the answer is the largest value cur takes during the scan; keep it in best. Initialise both with the first element rather than 0, so lists of only negative numbers return their largest element.

This is Kadane's algorithm, a dynamic programme whose state is a single number, giving one pass and constant memory.

Complexity

• Time: O(n)
• Space: O(1)

Python

class Solution:
    def maxSubArray(self, nums):
        cur = best = nums[0]
        for x in nums[1:]:
            # Extend the previous run, or start fresh if it would only drag x down.
            cur = max(x, cur + x)
            best = max(best, cur)
        return best

JavaScript

var maxSubArray = function(nums) {
  let cur = nums[0], best = nums[0];
  for (let i = 1; i < nums.length; i++) {
    // Extend the previous run, or start fresh if it would only drag nums[i] down.
    cur = Math.max(nums[i], cur + nums[i]);
    best = Math.max(best, cur);
  }
  return best;
};

What the interviewer is checking

It is a classic test of turning an O(n²) search into a one-pass DP by defining the right subproblem ("best ending here") and explaining why negative prefixes can be dropped.

Mistakes to avoid

• Initialising the best sum to 0, which returns 0 for all-negative input.
• Resetting the running sum to 0 before updating the best, which loses single-element answers.
• Confusing subarray (contiguous) with subsequence (any elements).

Follow-ups to expect

• Can you also return the start and end indices? (Record start when restarting.)
• Solve it with divide and conquer. (Combine best crossing the midpoint, O(n log n).)
• What if the array is circular? (Also consider total minus minimum subarray.)

In real software

Finding the most profitable stretch in a series of daily gains and losses, or the strongest region in a signal or genome score track, is this exact computation.

Practice next