Maximum Subarray (LeetCode 53)

The problem

Given an integer array nums (at least one element, values can be negative), return the largest sum of any contiguous, non-empty subarray.

Input:  nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6

The subarray [4, -1, 2, 1] sums to 6, and no other contiguous run does better.

How to think about it

Start with brute force. Try every start i and every end j, summing as you go. With a running sum that is O(n²), and O(n³) if you re-sum each range. For 10⁵ elements that is far too slow.

The key insight: fix where the subarray ends. Let cur be the best sum of a subarray that ends exactly at the current element. Any such subarray is either the element alone, or the best subarray ending one place earlier with this element added. So cur = max(x, cur + x). If the previous run has gone negative, it can only drag x down, so you start fresh at x.

The answer is the best cur ever seen. The best subarray ends somewhere, so tracking best = max(best, cur) over all positions finds it. This is Kadane’s algorithm, and it is really a 1-D DP where dp[i] = best sum ending at i, with only the last value kept.

Which pattern is this? 1-D DP over prefixes. The tell is “best contiguous subarray”: defining the state as “ending here” gives a recurrence that only looks one step back.

Approach

1. Set both best and cur to nums[0] (so an all-negative array still returns its largest element).
2. For each later element x: set cur = max(x, cur + x), then best = max(best, cur).
3. Return best.

Solution

def max_subarray(nums):
    best = cur = nums[0]                          # cur = best sum of a subarray ending here
    for x in nums[1:]: cur = max(x, cur + x); best = max(best, cur)   # extend or restart
    return best
# max_subarray([-2,1,-3,4,-1,2,1,-5,4]) -> 6

Dry run

On [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

The run 4, -1, 2, 1 peaks at 6, so the answer is 6.

Complexity

• Time: O(n). One pass, constant work per element.
• Space: O(1). Only cur and best are kept (the slice nums[1:] makes a copy; iterate by index to avoid it if memory is tight).

Edge cases and pitfalls

• All negative ([-3, -1, -2]) returns -1. Initialising best = 0 is the classic bug: it would wrongly return 0 for an empty subarray, which is not allowed.
• Single element returns that element.
• Resetting cur to 0 instead of to x also breaks the all-negative case.
• Follow-up: return the indices. Record the start whenever you restart and the end whenever best improves.

Related problems

• Maximum Product Subarray (LeetCode 152): the same “ending here” state, but you must track both a max and a min.
• Best Time to Buy and Sell Stock (LeetCode 121): a one-pass running-best scan with the same flavour.
• Subarray Sum Equals K (LeetCode 560): contiguous subarray sums again, solved with prefix sums instead.