Maximum Subarray
Mediumcur = max(nums[i], cur + nums[i]) · Kadane's
Keep a running sum; if it ever drops below zero start fresh, and track the best total seen.
The idea
Scan left to right keeping the best sum of a subarray ending here. At each element decide whether to extend the previous run or start fresh from this element.
-2
1
-3
4
-1
2
1
-5
4
0
1
2
3
4
5
6
7
8
Step 1 of 47. Brute force: add up every subarray and keep the biggest sum. Values: -2, 1, -3, 4, -1, 2, 1, -5, 4.
1/47
Brute force
timeO(n²)spaceO(1)
Sum every subarray.
1// add up every subarray, keep the best2let best = -Infinity;3for (let i = 0; i < n; i++) {4 let sum = 0;5 for (let j = i; j < n; j++) {6 sum += nums[j];7 best = Math.max(best, sum);8 }9}Input
- array
- [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output
- best
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
- Output:
- 6
- Explanation:
- The subarray [4,-1,2,1] sums to 6.
Example 2
- Input:
- nums = [5, 4, -1, 7, 8]
- Output:
- 23
- Explanation:
- The whole array is best, summing to 23.
Example 3
- Input:
- nums = [-3, -1, -2]
- Output:
- -1
- Explanation:
- All negative, so pick the least-bad single -1.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.