21. Maximum Subarray
MediumAlgorithms~20 min
Given an array of numbers, find the contiguous subarray with the largest sum and return that sum.
The subarray must contain at least one number, so an all-negative array returns its least-negative value.
Examples
Example 1
- Input:
- nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
- Output:
- 6
- Why:
- The subarray [4, -1, 2, 1] sums to 6.
Example 2
- Input:
- nums = [-3, -1, -2]
- Output:
- -1
- Why:
- Every option is negative, so take the largest single value.
Constraints
1 <= nums.length <= 10000-10000 <= nums[i] <= 10000