Trading Stocks With a Transaction Fee

medium dp greedy

Problem

You can buy and sell freely, but each completed sale costs fee. Maximise total profit. Track two states per day — cash (not holding) and hold (holding) — updating each day with the better of staying or transacting.

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

Output8

Buy day 0 (1), sell day 3 (8 − 2 = 6 profit), buy day 4 (4), sell day 5 (9 − 4 − 2 = 3 profit) → total 8.

prices (comma-separated)

fee

def max_profit(prices, fee):
    cash = 0
    hold = -prices[0]
    for p in prices[1:]:
        cash = max(cash, hold + p - fee)
        hold = max(hold, cash - p)
    return cash

function maxProfit(prices, fee) {
  let cash = 0, hold = -prices[0];
  for (let i = 1; i < prices.length; i++) {
    cash = Math.max(cash, hold + prices[i] - fee);
    hold = Math.max(hold, cash - prices[i]);
  }
  return cash;
}

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int cash = 0, hold = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            cash = Math.max(cash, hold + prices[i] - fee);
            hold = Math.max(hold, cash - prices[i]);
        }
        return cash;
    }
}

int maxProfit(vector<int>& prices, int fee) {
    int cash = 0, hold = -prices[0];
    for (int i = 1; i < (int)prices.size(); i++) {
        cash = max(cash, hold + prices[i] - fee);
        hold = max(hold, cash - prices[i]);
    }
    return cash;
}

Time: O(n) Space: O(1)