Maximum Subarray
Part of Practice: Reach & Reset
You are given an array of integers nums. A subarray is a contiguous run of elements — no skipping allowed. Find the subarray with the largest sum and return that sum. The subarray must contain at least one number, so if every number is negative the answer is the single largest number.
Constraints that matter: up to 100,000 elements and values can be negative, so checking every possible subarray (there are about n²/2 of them) is too slow, and you cannot just skip negative numbers — sometimes a negative in the middle is worth keeping.
Examples
- Input:
- nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
- Output:
- 6
The subarray [4, -1, 2, 1] sums to 6. Note it keeps the -1: paying 1 to connect the 4 with the 2 and 1 is worth it.
- Input:
- nums = [1]
- Output:
- 1
- Input:
- nums = [-3, -1, -2]
- Output:
- -1
Every subarray has a negative sum, so the best choice is the single element -1.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.