Maximum Subarray
Find the contiguous subarray with the maximum sum.
Pattern fit
Kadane's algorithm is really a tiny DP: decide whether extending the previous subarray helps more than restarting here.
Key observation
At each position you only need the best subarray ending here, not every previous interval.
Target complexity
O(n) / O(1)
How to break down the solution cleanly
Kadane's algorithm is really a tiny DP: decide whether extending the previous subarray helps more than restarting here.
At each position you only need the best subarray ending here, not every previous interval.
Name the state in plain language.
List the decisions that can transition into the state.
Reference implementation
Python# Generic pattern template
# 1D DP
dp = [0] * (n + 1)
dp[0] = base
for i in range(1, n + 1):
dp[i] = transition(dp, i)
# 2D DP
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
dp[i][j] = transition(dp, i, j)
Common pitfalls
Resetting to zero blindly and failing all-negative arrays.
Mixing global best with local ending-here state.
Common follow-ups
How would you return the actual subarray range?
What changes if the array is circular?
Continue with related problems
Build repeatable depth inside the Dynamic Programming cluster before moving on.