DATA STRUCTURES • ALGORITHMS

Kadane's Algorithm

An efficient dynamic programming approach to find the maximum sum of a contiguous subarray within a one-dimensional array of numbers.

Time

O(N)

Space

O(1)

Key Principle 1

Handles negative numbers

Key Principle 2

Single pass through array

Key Principle 3

Dynamic Programming foundation

Key Principle 4

Global vs Local maximum tracking

KADANE_LAB
ARRAY:
Current Step
Initialize maxSum to -∞ and curSum to 0.
Playback
Speed
DP Trackers ⠿
CURRENT SUM0
GLOBAL MAX-∞
Kadane Logic ⠿
1int maxSum = INT_MIN, curSum = 0;
2for (int x : nums) {
3    curSum = max(x, curSum + x);
4    maxSum = max(maxSum, curSum);
5}
6return maxSum;
-2
[0]
1
[1]
-3
[2]
4
[3]
-1
[4]
2
[5]
1
[6]
-5
[7]
4
[8]

Loading Lab...

Kadane Algorithm

Kadane Algorithm

Kadane's Algorithm

Kadane's Algorithm