Best Time to Buy and Sell Stock With Cost


  • 0
    T

    You can make unlimited transactions, but each sell or buy has a fixed cost. For example:
    given the prices [1, 3, 6, 5, 8], cost = 1, the max profit is 5. To see this, you can buy at 1 and sell at 8 to get a profit of 7, minus the transaction cost 2, and the final result is 5.


  • 1
    L

    Same DP idea as in stock buy and sell with cooldown? We can maintain 4 variables:

    s_i: max profit so far sell at day i
    b_i: max profit so far buy at day i
    h_i: max profit so far hold at day i
    e_i: max profit so far being lazy at day i
    

    With the following recurrence relation: j denotes i-1 here, cb is buy cost, cs is sell cost, p_i is the price at day i

    • s_i = max(b_j, h_j, s_j + cs - p_j) - cs + p_i
    • b_i = max(e_j, s_j) - cb - p_i
    • h_i = max(h_j, b_j)
    • e_i = max(e_j, s_j)

  • 3
    H

    Thanks for offering this question! My DP idea:

    States:
    (1) If we are holding the stock at the end of day i, the max possible profit at the end of day i is recorded as: hold[i]
    (2) If we are holding nothing at the end of day i, the max possible profit at the end of day i is recorded as: empty[i]

    Transition Functions:

    hold[i] = Math.max(hold[i - 1], empty[i - 1] - prices[i] - buyCost)
    empty[i] = Math.max(empty[i - 1], hold[i - 1] + prices[i] - sellCost)
    

    And of course they can be simplified to O(1) space.


  • 0

    thx @HungryOrc !

    With your idea, I finish the code as below, and it is accepted!

        // buyCost = 0
        public int maxProfit(int[] prices, int fee) {
            if(prices == null || prices.length < 2) return 0;
            
            int[] hold = new int[prices.length];
            int[] empty = new int[prices.length];
            hold[0] = -prices[0];
            empty[0] = 0;
            for (int i = 1; i < prices.length; i++) {
                hold[i] = Math.max(hold[i - 1], empty[i - 1] - prices[i]);
                empty[i] = Math.max(empty[i - 1], hold[i - 1] + prices[i] - fee);
            }
            return empty[prices.length - 1];
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.