Maximum Subarray
Find the contiguous, non-empty stretch of nums with the largest sum, and return that sum.
Example 1
nums [-2,1,-3,4,-1,2,1,-5,4]
returns 6
The stretch [4, -1, 2, 1] adds up to 6.
Example 2
nums [-3,-1,-2]
returns -1
All negative: the best stretch is just [-1].
Constraints
1 <= len(nums) <= 100-100 <= nums[i] <= 100
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Arrays problems
- Next PermutationMedium
- Nudge Every ItemMedium
- Product of Array Except SelfMedium
- Range IncrementsMedium
- Rising TripleMedium
- Shortest Span to SortMedium
- Coins to Add for Every TotalHard
- Fewest Coins for the TeamHard