Maximum Subarray

Problem

Given an integer array nums, find the contiguous, non-empty subarray with the largest sum and return that sum.

• The array is non-empty and has at most 200,000 elements.
• Elements are integers with magnitude at most 50,000, so sums fit in 64 bits.

Examples

• nums = [3, -4, 5, 2, -1, 6, -8, 2] → 12. The subarray [5, 2, -1, 6].
• nums = [2, 9, -3, 4, 6] → 18. The whole array.
• nums = [-8, -2, -5] → -2. All negative, so the best subarray is the single element -2.

Hints

1. For each position, consider the best subarray that ends exactly there. How does it relate to the best subarray ending one position earlier?
2. Extending a previous subarray is only worth it if that subarray's sum is positive; otherwise start fresh.
3. This is Kadane's algorithm: best_ending_here = max(x, best_ending_here + x), and the answer is the max of those over all positions.