Maximum subarray sum
MediumStuck?
Show a hintHide the hint
Carry one number: the best sum ending here. It is either this element alone, or this element added to the best ending just before it.
The idea behind this problem
Next in this lesson
Best day to buy and sellGiven an array of integers, find the contiguous subarray with the largest sum and return that sum.
The array holds at least one element, and the subarray must not be empty, so an array of only negative numbers answers with its largest single value.
Constraints#
1 <= n <= 200000-10^9 <= nums[i] <= 10^9
Input
nums is a count then that many integers.
Output
A single integer, the largest subarray sum.
Examples
Input
9 -2 1 -3 4 -1 2 1 -5 4
Output
6
The subarray `4 -1 2 1` sums to 6, the largest possible.
Input
1 -1
Output
-1
Every element is negative, so the answer is the largest single value.
Something wrong with this problem? Report an issue
Ready to try it
Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.
Free, and it stays free. No card.