mediumArraysDynamic programming
Maximum Subarray Sum
Find the largest sum of any non-empty run of consecutive numbers in an array. Kadane's algorithm turns an O(n²) idea into a single pass.
By Deepak KumarTests checked by DeepakJavaScript or Python
Given an integer array nums, find the contiguous, non-empty subarray with the largest sum and return that sum.
A subarray is a run of neighbouring elements, such as [4, -1, 2] inside [1, 4, -1, 2, 5]. It must contain at least one element, so for an array of only negative numbers the answer is the largest single number.
Examples
Example 1
Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] Output: 6 Why: [4, -1, 2, 1] adds up to 6
Example 2
Input: nums = [-4, -2, -7] Output: -2 Why: All numbers are negative, so the best is the single largest one
Constraints
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4
Hints
Hint 1
For each position, what is the best sum of a subarray that ends exactly there?
Hint 2
The best subarray ending at i either extends the best one ending at i - 1, or starts fresh at i. Keep the overall maximum as you go.
Solution
Show the solution (try it yourself first)
Approach: Kadane's algorithm
Checking every start and end pair is O(n²). Instead, track cur, the best sum of a subarray that ends at the current position. At each number you either extend that run or start a new one there, whichever is larger: cur = max(x, cur + x). A negative running sum only drags things down, so it's dropped automatically. The answer is the largest cur seen. Starting from nums[0] rather than 0 is what makes all-negative arrays work.
function maxSubarraySum(nums) {
let best = nums[0], cur = nums[0];
for (let i = 1; i < nums.length; i++) {
cur = Math.max(nums[i], cur + nums[i]);
best = Math.max(best, cur);
}
return best;
}Complexity
Time O(n), space O(1). A common follow-up asks you to return the subarray itself: remember where the current run started whenever you begin a new one.