Best Time to Buy and Sell Stock with Transaction Fee

Share

Given prices[] and a transaction fee, find the maximum profit from unlimited transactions (each transaction costs fee). You must sell before you buy again.

Example 1
Input: prices=[1,3,2,8,4,9], fee=2 → Output: 8
Example 2
Input: prices=[1,3,7,5,10,3], fee=3 → Output: 6

Solution Approach

Two states: hold (holding stock) and cash (not holding). Transition: cash = max(cash, hold + price - fee); hold = max(hold, cash - price).

  • Initialize cash=0, hold=-prices[0].
  • For each price: new_cash = max(cash, hold + price - fee); new_hold = max(hold, cash - price).
  • Return cash.
Java
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int cash = 0, hold = -prices[0];
        for (int price : prices) {
            int newCash = Math.max(cash, hold + price - fee);
            hold = Math.max(hold, cash - price);
            cash = newCash;
        }
        return cash;
    }
}
  • Time Complexity: O(N)
  • Space Complexity: O(1)