Medium · Take or Skip DP
Understand → Visualise → Practice.
Taking a value prevents taking its immediate neighbour. The best prefix answer keeps separate states for taking and skipping the current position.
newTake = oldSkip + value; newSkip = max(oldSkip, oldTake).
take and skip describe the processed prefix.
Compute both from the old states.
Return max(take, skip).
O(n) time and O(1) space.
Update both states simultaneously; overwriting skip early loses the previous value needed for take.
Read the full guide first: Dynamic Programming.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.