AlgoViz
HomeArrays & Hashing

Kadane's Algorithm

Medium

Drop the prefix the moment it turns negative

Problem

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum, and return that sum.

In simple words

Carry a running sum; drop it whenever it goes negative, and remember the best total seen.

The idea

Carry a running sum and reset it to zero whenever it goes negative, tracking the best value seen. A negative prefix can only hurt whatever follows, so discarding it is always at least as good as keeping it.

The trick

  • Record the best before resetting, or an all-negative array reports 0 instead of the largest element.
  • Reset when the running sum drops below zero, not when the element is negative.
  • O(n) single pass, O(1) space.
-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.

Constraints

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

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.