Maximum subarray sum (Kadane)
Coding problemMediumAsked in: Adobe, Amazon, Flipkart, Google, Microsoft, Oracle
Given a non-empty list of integers, find the run of one or more neighbouring values (a subarray) with the largest sum, and return that sum.
Values can be negative. If every value is negative, the answer is the largest single value, because the run must hold at least one value.
Examples
Example 1
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
The run 4, -1, 2, 1 adds up to 6.
Example 2
Input: nums = [5,4,-1,7,8]
Output: 23
Example 3
Input: nums = [-3,-2,-5]
Output: -2
Constraints
- The list holds between 1 and 100,000 integers
- Each value is between -10,000 and 10,000
Run checks the 3 examples. Submit also runs the hidden tests: edge cases, large inputs and a time limit.
Run your code to see the results here. Ctrl or Cmd + Enter runs; add Shift to submit.