Best Time to Buy and Sell Stock with Transaction Fee

Problem in plain words

You know a stock's price for each day and may trade as many times as you like, but you can hold at most one share at a time, and every completed buy-and-sell round costs a fixed fee. Find the maximum total profit.

For example, with prices [1, 4, 2, 8] and fee 1, buying at 1 and selling at 8 earns 7 - 1 = 6, while two rounds (1 to 4, then 2 to 8) earn 2 + 5 = 7, which is better.

Intuition

At the end of any day you are in one of two states: holding a share or holding cash only. Track the best profit for each state. Tomorrow's cash is either today's cash (do nothing) or today's holding plus the price minus the fee (sell). Tomorrow's holding is either today's holding (keep it) or today's cash minus the price (buy). This 'small set of states updated per item' style is the same choose-or-skip thinking behind the 0/1 knapsack DP lesson.

Approach

1. State: cash is the best profit with no share in hand; hold is the best profit while holding one share (the purchase price is already subtracted).
2. Recurrence: cash = max(cash, hold + price - fee) and hold = max(hold, cash - price).
3. Base case: before day 0's update, cash = 0 and hold = -prices[0] (buying on the first day).
4. Order: process days 1 to n - 1. Using the freshly updated cash in the hold update is safe: it means selling and re-buying on the same day, which only loses the fee and is never chosen over keeping the share.
5. Return cash, since ending with a share in hand is never better.

Dry run

Input: prices = [2, 5, 1, 6], fee = 2. Start: cash = 0, hold = -2.

The answer is 4: buy at 2, sell at 5 (profit 1 after fee), buy at 1, sell at 6 (profit 3 after fee).

Java solution

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int cash = 0;            // best profit holding no share
        int hold = -prices[0];   // best profit holding one share
        for (int i = 1; i < prices.length; i++) {
            cash = Math.max(cash, hold + prices[i] - fee);   // sell today
            hold = Math.max(hold, cash - prices[i]);         // buy today
        }
        return cash;
    }
}

Python solution

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        cash, hold = 0, -prices[0]
        for price in prices[1:]:
            cash = max(cash, hold + price - fee)   # sell today
            hold = max(hold, cash - price)         # buy today
        return cash

Complexity

Edge cases and common mistakes

• Falling prices: no trade is profitable, cash stays 0, which is the right answer.
• Charging the fee twice: apply it once per round trip, either when buying or when selling, never both.
• Greedy 'sell on every rise': that works for the fee-free version but here many small trades each pay the fee, so it overtrades.
• Single day: the loop does not run and the answer is 0.