53. Maximum Subarray
Your function receives an integer array nums and returns the largest possible sum of a contiguous, non-empty run of its elements.
A run (subarray) keeps the original order and skips nothing: pick a start index and an end index and add up everything between them, inclusive. Because at least one element must be taken, the answer to an all-negative array is its single largest element — not zero.
Only the best sum is wanted, never the run itself, and that number is unique even when several different runs achieve it.
Example 1:
Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Explanation: The run [4, -1, 2, 1] sums to 6; no other contiguous run beats it.
Example 2:
Input: nums = [5, 4, -1, 7, 8]
Output: 23
Explanation: With mostly positive numbers, taking the whole array (sum 23) is best.
Example 3:
Input: nums = [1]
Output: 1
Explanation: A single element is its own best run.
Constraints:
- 1 ≤ nums.length ≤ 10⁵
- -10⁴ ≤ nums[i] ≤ 10⁴
Hints:
A sum that has gone negative can only hurt whatever comes after it. Would you ever carry a negative running total forward?
Sweep once, keeping best-run-ending-here: for each element, either extend the previous run or restart at the element alone — cur = max(x, cur + x). The answer is the largest cur seen. This is Kadane's algorithm.
For the divide-and-conquer route (worth knowing for follow-ups): a best run either lives in the left half, lives in the right half, or crosses the middle — and the crossing case is best-suffix-of-left + best-prefix-of-right.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Expected output: 6