Largest Sum Subarray
You get an integer array nums. A subarray is a group of one or more elements that sit next to each other in the array.
Return the largest sum of any subarray.
Note
The subarray must have at least one element. So if every value is negative, the answer is the largest single value, not 0.
Hint
Walk through the array once. For each position, keep the best sum of a subarray that ends at this position. It is either the current value alone, or the current value added to the best sum that ended one step before. The answer is the largest of these. This takes O(n) time.
Examples
Example 1
- Input:
- [3,-7,4,-1,5,-9,2]
- Output:
- 8
The subarray [4, -1, 5] adds up to 8. No other subarray has a larger sum.
Example 2
- Input:
- [-6,-2,-9,-4]
- Output:
- -2
Every value is negative. The best subarray is [-2] by itself.
Example 3
- Input:
- [2,3,-1,6]
- Output:
- 10
Taking the whole array gives 2 + 3 - 1 + 6 = 10. The -1 is worth keeping because the 6 after it is larger.
Constraints
1 <= nums.length <= 40-100 <= nums[i] <= 100
Run checks your code against the 3 examples. Submit checks it against all 303 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.