JavaScriptMediumArrays20 min
Find the maximum contiguous subarray sum
Return the largest sum of a nonempty contiguous subarray; return null for an empty array. All input is valid JSON satisfying the constraints; do not mutate the meaning of values through type coercion. Interviewers use this problem to assess use Kadane's recurrence for the best sum ending at each index.
Input
A JSON array of integers on stdin.
Output
Print one compact JSON value: an integer sum or null.
Constraints
0 <= array length <= 10000; integers between -1000000 and 1000000.
Example
Input
[-2,1,-3,4,-1,2,1,-5,4]
Output
6
Example 2 input
[0,0]
Output
0
Boundary case: All-negative arrays still require a nonempty subarray
Public test cases (2)
Input
[-2,1,-3,4,-1,2,1,-5,4]
Expected output
6
Input
[1,2,3]
Expected output
6
Hints (2)
- Either extend the previous subarray or start at the current value
- All-negative arrays still require a nonempty subarray
Target complexity: time O(n) · space O(1)