Obsidian Notes

Best Time to Buy and Sell Stock with Transaction Fee

3 min read

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.

Note:

  • You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
  • The transaction fee is only charged once for each stock purchase and sale.

Example 1:

Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:

  • Buying at prices[0] = 1
  • Selling at prices[3] = 8
  • Buying at prices[4] = 4
  • Selling at prices[5] = 9
    The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

Example 2:

Input: prices = [1,3,7,5,10,3], fee = 3
Output: 6

Constraints:

  • 1 <= prices.length <= 5 * 104
  • 1 <= prices[i] < 5 * 104
  • 0 <= fee < 5 * 104

Approach - Space Optimized 2 pointer

  • We use two pointer and we use max in sold because it is sometime better to hold because there is a fees now
  • o(n), O(1)
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int sold = 0, hold = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            sold = Math.max(sold, hold + prices[i] - fee);
            hold = Math.max(hold, sold - prices[i]);
        }
        return sold;
    }
}

Approach - Memoization

  • Similar just use the stored solution where required
class Solution {
    public static final int BUY = 0;
    public static final int SELL = 1;
    public int[][] dp;
    public int maxProfit(int[] prices, int fee) {
        dp = new int[prices.length + 1][2];
        for (int[] a: dp)
            Arrays.fill(a,-1);
        return solve(prices, 0, fee, BUY);    
    }
 
    public int solve(int[] prices, int day, int fee, int action) {
        if (day >= prices.length)
            return 0;
        
        if (dp[day][action] != -1)
            return dp[day][action];
 
        int profit = 0;
        if (action == BUY) {
            int consider = solve(prices, day+1, fee, SELL) - prices[day];
            int not_consider = solve(prices, day+1, fee, BUY);
            profit = Math.max(consider, not_consider);
        } else {
            int consider = prices[day] + solve(prices, day+1, fee, BUY) - fee;
            int not_consider = solve(prices, day+1, fee, SELL);
            profit = Math.max(consider, not_consider);
        }
 
        return dp[day][action] = profit;
    }
}

Approach - Recursion

  • same approach just subtract the fee and also no day + 2 since we don’t have cooldown
class Solution {
    public static final int BUY = 0;
    public static final int SELL = 1;
 
    public int maxProfit(int[] prices, int fee) {
        return solve(prices, 0, fee, BUY);    
    }
 
    public int solve(int[] prices, int day, int fee, int action) {
        if (day >= prices.length)
            return 0;
        
        int profit = 0;
        if (action == BUY) {
            int consider = solve(prices, day+1, fee, SELL) - prices[day];
            int not_consider = solve(prices, day+1, fee, BUY);
            profit = Math.max(consider, not_consider);
        } else {
            int consider = prices[day] + solve(prices, day+1, fee, BUY) - fee;
            int not_consider = solve(prices, day+1, fee, SELL);
            profit = Math.max(consider, not_consider);
        }
 
        return profit;
    }
}

Backlinks