Maximum Subarray
MediumGreedy · NVIDIA
You are given an integer array nums. Return the largest possible sum of a non-empty contiguous subarray (one or more consecutive elements).
Because the subarray cannot be empty, the answer is negative when every number is negative.
Example 1
- Input:
- nums = [-8, 3, 4, -2, 5]
- Output:
- 10
- Explanation
- The best run is
3, 4, -2, 5, summing to 10. Crossing the-2is worth it because the5after it more than makes up for it.
Example 2
- Input:
- nums = [-4, -2, -7]
- Output:
- -2
- Explanation
- Every value is negative, so the best you can do is the single least negative value,
-2. Adding more elements only lowers the sum.
Example 3
- Input:
- nums = [6, -7, 5]
- Output:
- 6
- Explanation
- Keeping
6alone gives 6. Extending to6, -7, 5gives only 4, and5alone gives 5, so the answer is 6.
Constraints
- 1 ≤
nums.length≤ 105 - -104 ≤
nums[i]≤ 104