arrays · Problem 2 of 3
Maximum Subarray
medium
Amazon
Microsoft
Meta
AmazonMicrosoftMetaReturn the largest sum obtainable from any contiguous subarray of nums. The array has at least one element.
maxSubarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) -> 6Your solution
Runs your code and animates it without grading anything. Change the input to see what it does on a case the tests do not cover.
Running is free — Submit is what records it. Or press ⌘↩
Tests
4 cases, 1 hidden| call | type | expected | result |
|---|---|---|---|
| maxSubarray([-2,1,-3,4,-1,2,1,-5,4]) | mixed | 6 | — |
| maxSubarray([-3,-1,-2]) | all negative | -1 | — |
| maxSubarray([1,2,3]) | all positive | 6 | — |
| withheld | hidden | withheld | — |
Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.
Complexity
- target time
- O(n)
- target space
- O(1)
Kadane's algorithm. The brute force over every pair of endpoints is O(n^2); the insight that kills the inner loop is that a negative running sum is never worth keeping.
Hints
Stuck? Hints open one at a time, each giving a little more away.
3 hints left