loading

714. Best Time to Buy and Sell Stock with Transaction Fee — Step-by-Step Visualization

mediumLeetCode #714ArrayDynamic ProgrammingGreedy

You are given an array `prices` where `prices[i]` is the price of a stock on day `i`, and an integer `fee` representing a transaction fee. Find the maximum profit. You may complete as many transactions as you like, but you must pay the `fee` for each transaction. You may not buy and sell on the same day. **Example:** Input: `prices = [1,3,2,8,4,9]`, `fee = 2` Output: `8` Explanation: Buy at 1, sell at 8 (profit 5). Buy at 4, sell at 9 (profit 3). Total = 8.

Algorithm Pattern

Two-State DP

Key Idea

Track two states per day: `hold` (max profit while holding a stock) and `cash` (max profit without a stock). Transition: hold = max(hold, cash - price); cash = max(cash, hold + price - fee).

Step-by-Step Approach

  1. Initialize hold = -prices[0], cash = 0.
  2. For each subsequent price p:
  3. hold = max(hold, cash - p) ← buy today or keep holding.
  4. cash = max(cash, hold + p - fee) ← sell today (pay fee) or stay out.
  5. Return cash.

Common Gotchas

  • Update hold before cash in the same iteration — cash uses the new hold value, which is fine (you can't buy and sell on the same day because buying sets hold < 0).
  • Fee is paid on sell, not buy — subtract it when transitioning from hold to cash.

Related Problems

← All problems