Kadane / Running Optimum
At each index decide whether to extend the previous best or restart from here. One pass, two variables.
Dynamic ProgrammingO(n) time, O(1) spaceNew4 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
maximum subarray sum
best profit in one transaction
max product subarray
The template
Get this into muscle memory, then adapt the condition per problem.
let cur = a[0], best = a[0];
for (let i = 1; i < n; i++) {
cur = Math.max(a[i], cur + a[i]);
best = Math.max(best, cur);
} Watch Kadane (Maximum Subarray)If you are stuck
The generic hint ladder for this pattern, in order.
- 1What is the best subarray that ends exactly at index i?
- 2A negative running total is never worth carrying forward.
- 3Track the global best separately from the running best.
Drill it
Every problem in the bank that uses this pattern.
0 / 4 solved