Problem
Given an integer array:
[-2, 1, -3, 4, -1, 2, 1, -5, 4]Find the maximum sum of any contiguous subarray.
Example:
[4, -1, 2, 1]Sum:
6State Design
Define:
dp[i]Meaning:
Maximum subarray sum ending exactly at index i.Important:
ending exactly at iNot:
Best answer so far.The wording of the state determines the recurrence and where the final answer is stored.
Transition
At position i, there are only two choices.
Start a new subarray
nums[i]Extend the previous subarray
dp[i-1] + nums[i]Choose the better one:
dp[i]
=
max(
nums[i],
dp[i-1] + nums[i]
)Base Case
dp[0] = nums[0]Example
Array:
2 -1 3 -2Compute:
dp[0] = 2
dp[1]
= max(-1, 2 + (-1))
= 1
dp[2]
= max(3, 1 + 3)
= 4
dp[3]
= max(-2, 4 + (-2))
= 2Result:
nums: 2 -1 3 -2
dp: 2 1 4 2Final Answer
Notice:
dp[i]means:
Best subarray ending exactly at i.Therefore the optimal subarray may end anywhere.
Final answer:
max(dp)Example:
max(2,1,4,2)
=
4Subarray:
[2,-1,3]Why Not dp[n-1]?
Compare with House Robber.
House Robber
State:
dp[i]
=
Best answer considering houses [0..i]Final answer:
dp[n-1]because the state already represents the global optimum up to that point.
Kadane
State:
dp[i]
=
Best subarray ending exactly at i.The optimal subarray is not required to reach the final element.
Therefore:
Answer = max(dp)Key Insight
Always ask:
What does my state represent?The answer location follows naturally.
Examples:
Fibonacci
fib(n)
House Robber
dp[n-1]
Coin Change
dp[target]
Knapsack
dp[n][W]
(or dp[W] after compression)
LCS
dp[0][0]
Edit Distance
dp[0][0]
Kadane
max(dp)The most common DP mistake is not the recurrence.
It is misunderstanding what each state means.
Lessons Learned
-
The DP state meaning is more important than the formula.
-
Similar-looking
dp[i]states can represent completely different subproblems. -
The final answer is not always stored in the last state.
-
Before writing code, identify:
-
State
-
Transition
-
Base case
-
Which state contains the final answer?
-