Maximum Subarray Sum
Intermediate
Given a non-empty list of integers nums, return the largest sum of a contiguous run of one or more elements (a subarray).
The starter code tries every start and end. It is correct but too slow for long lists. Make it fast.
Examples
Example 1
Input:
max_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4])
Output:
6
The best run is [4, -1, 2, 1] with sum 6.
Example 2
Input:
max_subarray_sum([-3, -1, -2])
Output:
-1
All values are negative, so the best run is the single element -1.
Constraints
1 <= len(nums) <= 2 * 10**5-10**4 <= nums[i] <= 10**4- The subarray must contain at least one element.
Theory
Go to TheoryKeywords
dsa-sheetbasicsmake-it-fast
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.