← All problemsExample 1 Example 2
Problem
Maximum Subarray
Medium- arrays
- dynamic-programming
Return the greatest sum that a contiguous run of elements in nums can have. A run must contain at least one element, so it cannot be empty.
- Input
nums = [3, -5, 4, 2, -1, 6, -8, 2]- Output
11- Explanation
the run
[4, 2, -1, 6]adds up to 11, and no other run does better.
- Input
nums = [-7, -3, -9]- Output
-3- Explanation
every value is negative, so a longer run only lowers the sum. The best run is the single largest element.
Constraints:
1 <= nums.length <= 10^5-10^3 <= nums[i] <= 10^3
Follow-up: checking every run takes O(n^2) or worse. Can you do it in a single pass?
Tab indents. Press Esc, then Tab to leave the editor.
Ctrl or ⌘ + Enter runs the tests.
Run your code to see every test here. Nothing is submitted or recorded.