Maximum Subarray

Medium · Greedy

You are given an array of integers. Find a contiguous run of elements (at least one element) whose sum is as large as possible, and return that maximum sum. The array can contain negative numbers, so sometimes the best choice is a single element rather than a longer run.

Examples

Input:  nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Why:    The subarray [4,-1,2,1] sums to 6, which is the largest possible sum of any contiguous run.

Input:  nums = [1]
Output: 1
Why:    With only one element, that element itself is the answer.

Input:  nums = [-1,-2,-3]
Output: -1
Why:    All elements are negative, so the best run is the single largest element, -1.

Constraints

1 <= nums.length <= 10^5, -10^4 <= nums[i] <= 10^4

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Maximum Subarray

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Maximum Subarray. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.