Dynamic Programming • 1D Arrays

Kadane's Algorithm

Find the contiguous subarray with the largest sum in O(N) time. The quintessential space-optimized DP algorithm.

Overview

Kadane's algorithm is functionally a DP algorithm optimized from O(N) space to O(1) space. It answers: "Should I add the current element to my existing sequence, or start a new sequence?"

The DP State

Conceptually, `dp[i] = max(nums[i], nums[i] + dp[i-1])`. If `dp[i-1]` is negative, `nums[i]` on its own is better.

The Reset

Instead of an array, we track `curSum`. If `curSum` ever drops below zero, it will mathematically drag down any future elements. So we reset it to 0.

Global Max

Because the max subarray could be anywhere in the middle, we constantly update `maxSum` with the highest `curSum` we've ever seen.

-2

1

-3

4

-1

2

1

-5

4

Current Sum

0

Max Sum

-∞

Code Tracker

:::

1let curSum = 0;

2let maxSum = -Infinity;

3for (let i = 0; i < nums.length; i++) {

4 curSum += nums[i];

5 if (curSum > maxSum) maxSum = curSum;

6 if (curSum < 0) curSum = 0;

7}

8return maxSum;

Kadanes Algorithm Dp

Kadanes Algorithm Dp

Kadane's Algorithm

Overview

The DP State

The Reset

Global Max

Kadane's Algorithm

Overview

The DP State

The Reset

Global Max