Best Time to Buy and Sell Stock with Transaction Fee

medium dp greedy

Problem

You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee. Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.

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;
}

Explanation

Unlimited trades are allowed, but each completed trade costs a fee. We track two states day by day: cash = best profit when we currently hold no share, and hold = best profit when we currently own a share (counting the money spent to buy it).

Each day we update both. cash = max(cash, hold + p - fee) says either stay in cash, or sell today's share for price p and pay the fee. hold = max(hold, cash - p) says either keep holding, or buy today by spending p from our cash position.

We only charge the fee on selling, so each round trip pays it exactly once. Starting values are cash = 0 and hold = -prices[0] (as if we bought on day 0).

The final answer is cash, since ending while holding a share is never better than having sold.

Example: prices = [1,3,2,8,4,9], fee = 2. Buy@1 sell@8 (8−1−2 = 5), buy@4 sell@9 (9−4−2 = 3), total 8.

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