Skip to content
Hello Python

Track Stock State with a Fee

Practice ExerciseIntermediateMediumState-machine DPArray

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement max_profit_with_fee(prices, fee). You may hold at most one share, buy and sell any number of times, and pay fee on each sale. Return the maximum final cash. Empty prices returns 0.

Starter code

def max_profit_with_fee(prices, fee):
    pass
Test cases

multiple-trades

{
  "args": [
    [
      1,
      3,
      2,
      8,
      4,
      9
    ],
    2
  ]
}

Expected: 8

no-profit

{
  "args": [
    [
      5,
      4,
      3
    ],
    1
  ]
}

Expected: 0

Wizard outline
  1. Step 1: Define day-zero states

    Represent cash and holding after the first price. The state meaning must be explicit before transitions can be compared.

  2. Step 2: Solve one buy-and-sell transition

    Establish the fee-aware transition for one completed transaction. A single-transaction baseline isolates the buy/sell arithmetic before the state machine composes repeated cycles.

  3. Step 3: Carry states across all days

    Complete the contract for multiple profitable transactions. The two-state recurrence automatically composes any number of legal buy/sell cycles.

Footguns and prerequisites
  • Returning holding state includes an unsold share.
  • Updating hold from newly updated cash can perform invalid same-step transitions.
  • dynamic programming
Reviewed references
Recommended approach and implementation

Maintain the best realized cash and best wealth while holding one share, updating them simultaneously for each price.

Why it works: The two states cover every legal end-of-day position. Each transition considers exactly staying or making the one legal trade into that state, so induction over days yields optimal state values and final cash.

def max_profit_with_fee(prices, fee):
    if not prices:
        return 0
    cash = 0
    hold = -prices[0]
    for price in prices[1:]:
        next_cash = max(cash, hold + price - fee)
        next_hold = max(hold, cash - price)
        cash, hold = next_cash, next_hold
    return cash