DSAverse

Dynamic Programming

Loading Dynamic Programming...

DP Table Filling

subproblems

O(2^n)→O(n)

Maximum Subarray

Kadane's algorithm finds the contiguous subarray with the largest sum in a single pass, by asking one question at every element: extend, or start over?

Time: O(n)

Space: O(1)

Optimized DP

Running Sum

Array (comma-separated, negatives welcome):

Speed: 1000ms

Fast (300ms)Slow (2000ms)

Step 1 of 0Phase: start

Running Sum

max ending here

Best Sum

—

answer so far

Array

-2

-3

-1

-5

current elementrunning subarraybest so far

Max Ending Here — the running sum at each index

dp[0]

—

dp[1]

—

dp[2]

—

dp[3]

—

dp[4]

—

dp[5]

—

dp[6]

—

dp[7]

—

dp[8]

—

Current Step

Click Play to begin

Algorithm Details

Time:O(n)

Space:O(1)

Passes:1

Type:Optimized DP

Key Concepts

Recurrence: cur = max(nums[i], cur + nums[i])
Insight: a negative carried sum can only hurt, so drop it
Seed: start both sums at nums[0], never 0
Why it is DP: dp[i] is the best subarray ending exactly at i

Knowledge Check

Question 1 of 3