Problem. Given an integer array nums, return the largest possible sum of a non-empty contiguous subarray.
This is the classic one-dimensional DP pattern.
Examples:
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]→6nums = [1]→1nums = [5, 4, -1, 7, 8]→23
Solution. At each index, decide whether the best subarray ending here should extend the previous run or start fresh at the current value. The global maximum over those endpoint answers is the result.
def max_subarray(nums):
best_ending_here = nums[0]
best_overall = nums[0]
for value in nums[1:]:
best_ending_here = max(value, best_ending_here + value)
best_overall = max(best_overall, best_ending_here)
return best_overall
O(n) time, O(1) space.
Gotchas.
- The subarray must be non-empty, so the all-negative case should return the least negative value.
- Tracking only the global sum misses the required contiguity constraint.
- If you also need the interval itself, store start and end pointers when you reset or improve the best sum.