Linear and Sequence DP

What is this?

Every problem here walks a sequence once. What distinguishes them is what has to travel alongside the index: whether you currently hold a stock, whether you took a value and therefore destroyed its neighbours, which jump sizes are still available, or whether the next jump must be odd or even. Get the second component of the state right and each recurrence is one or two lines.

💡 Fun fact: Delete and Earn is House Robber wearing a disguise. Taking the value v deletes every v−1 and v+1, so if you index by value instead of by array position, "cannot take adjacent values" is literally the robber's "cannot rob adjacent houses" — with each house worth v × count(v). No new algorithm, just a change of coordinate. Spotting that a problem is a known one under a re-indexing is a faster route to a correct answer than deriving a fresh recurrence, and interviewers notice it immediately.

🔓 The 6 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: the index is never the whole state. Name the second component — holding, taken, jump size, parity — and the recurrence writes itself.

1. Two states chasing each other

cash, hold = 0, -prices[0]                  # cash: own nothing.  hold: own one share
for p in prices[1:]:
    cash = max(cash, hold + p - fee)        # sell today (pay the fee once, on sale)
    hold = max(hold, cash - p)              # buy today
return cash

Charging the fee on the sale rather than the purchase keeps it to one deduction per completed round trip. And hold is updated using the new cash, which correctly forbids buying and selling on the same day — the sale must have happened strictly earlier.

The answer is cash, never hold: ending while still holding a share can never beat having sold it.

2. Re-index, then rob houses

pts = Counter(nums)
take, skip = 0, 0
for v in sorted(pts):
    if v - 1 in pts:                        # adjacent value → cannot take both
        take, skip = skip + v * pts[v], max(take, skip)
    else:                                   # gap → no constraint
        take, skip = max(take, skip) + v * pts[v], max(take, skip)
return max(take, skip)

Iterating over the sorted distinct values, not over 1 … max, keeps this O(n log n) even when the values are enormous. The v − 1 in pts test is what distinguishes a real adjacency from a gap in the value line — and getting it wrong turns a correct solution into one that refuses free money.

3. When the transitions come from a stack

Odd Even Jump is not a DP over values but over reachability, computed backwards:

odd[i]  = even[next_greater_or_equal[i]]    # odd jumps go up
even[i] = odd[next_smaller_or_equal[i]]     # even jumps go down

Both "next" arrays are next-greater-element problems solved with a monotonic stack over indices sorted by value — sorting by value turns "the smallest value ≥ this one" into an ordinary next-greater scan. The DP itself is then two lines, running right to left because a jump always moves forward.

4. The stack that is not a DP at all

Longest Valid Parentheses has a clean O(n) DP, and an even cleaner stack solution:

st, best = [-1], 0                          # -1 is the base of the current valid run
for i, ch in enumerate(s):
    if ch == '(': st.append(i)
    else:
        st.pop()
        if not st: st.append(i)             # unmatched ')' becomes the new base
        else: best = max(best, i - st[-1])

The sentinel -1 is what lets i - st[-1] measure a run that starts at index 0 without a special case. Knowing both the DP and the stack version — and saying which you prefer and why — is worth more than either alone.

5. A 30-second worked example (stock with fee)

prices = [1, 3, 2, 8, 4, 9], fee = 2

start          cash =  0   hold = -1
p = 3          cash = max(0, -1+3-2) =  0     hold = max(-1,  0-3) = -1
p = 2          cash = max(0, -1+2-2) =  0     hold = max(-1,  0-2) = -1
p = 8          cash = max(0, -1+8-2) =  5     hold = max(-1,  5-8) = -1
p = 4          cash = max(5, -1+4-2) =  5     hold = max(-1,  5-4) =  1
p = 9          cash = max(5,  1+9-2) =  8     hold = max( 1,  8-9) =  1

answer: 8

Two transactions — buy at 1, sell at 8, buy at 4, sell at 9 — for 7 + 5 = 12 gross and two fees, giving 8. Watch the step at p = 4: hold becomes 1 only because cash was already 5, which is the mechanism that stops the same share being bought and sold on one day.

6. Where you'll actually meet this

• Trading systems. Transaction fees are the reason naive buy-low-sell-high strategies lose money.
• Loyalty and rewards. "Redeem this tier and adjacent tiers are locked" is Delete and Earn.
• Compiler and editor tooling. Longest balanced region is bracket matching in a real parser.
• Version and dependency chains. Longest increasing subsequence underlies patch-ordering and compatibility questions.
• Game and physics simulation. Frog Jump is a constrained state-space reachability search in disguise.

7. Problems in this chapter

▶ Best Time to Buy and Sell Stock with Transaction Fee

Maximum profit with a fee per transaction. Carry two states — holding and not holding — and update them in that order.
Pattern: two-state linear DP. Target: O(n) time, O(1) space.

▶ Delete and Earn

Take a value and lose its neighbours. Index by value rather than position and the problem becomes House Robber.
Pattern: re-indexed House Robber. Target: O(n log n) time, O(1) extra space.

▶ Frog Jump

Cross a river where the next jump is within one of the last. State is (stone, jump size), stored as a set per stone.
Pattern: reachability DP with a compound state. Target: O(n²) time and space.

▶ Longest Increasing Subsequence

The classic, at its O(n log n) bound. Maintain the smallest possible tail for each length and binary-search the insertion point.
Pattern: patience sorting. Target: O(n log n) time, O(n) space.

▶ Longest Valid Parentheses

Longest balanced substring. Either a DP on match positions or a stack of indices with a sentinel base.
Pattern: stack with an index sentinel. Target: O(n) time and space.

▶ Odd Even Jump

Count indices from which the end is reachable under alternating jump rules. Precompute next-greater and next-smaller with a monotonic stack, then a two-line DP backwards.
Pattern: monotonic stack + reachability DP. Target: O(n log n) time, O(n) space.

8. Common pitfalls 🚫

• Charging the fee twice. Deduct it once per completed transaction — on the sale.
• Updating hold from the old cash, which permits buying and selling on the same day.
• Iterating 1 … max(nums) in Delete and Earn, which explodes on large values. Iterate the distinct values.
• Missing the gap case. When v − 1 is absent there is no constraint and you take both.
• Storing only "reachable" in Frog Jump. The jump size that got you there is part of the state.
• Forgetting the -1 sentinel in the parentheses stack, which breaks every run starting at index 0.
• Sorting by value without an index tie-break in Odd Even Jump — equal values must resolve to the smaller index.

9. Key takeaways

1. The index alone is never the state in this chapter — name what travels with it.
2. Re-indexing can turn a new problem into a known one. Value, not position.
3. Update order encodes the rules. cash before hold forbids same-day round trips.
4. A monotonic stack can supply DP transitions as easily as it answers next-greater queries.
5. Sentinels remove edge cases — one -1 replaces a special case for index 0.
6. Know both solutions where two exist, and be able to say which you prefer.
7. Why interviewers like it: these all look one-dimensional and none of them are, so the state choice is the entire signal.

Order: Best Time to Buy and Sell Stock with Transaction Fee → Delete and Earn → Frog Jump → Longest Increasing Subsequence → Longest Valid Parentheses → Odd Even Jump.