c++ O(n) time, O(1) space dp, with explanation and example


  • 0
    Q

    For [1,4,3,7], 2
    When we visit price 4, it is obvious we sell at 4 and buy at 1
    When we visit 7, we have two choices:

    1. We sell at 7 and buy at 1, which results profit = 7 - 1 - 2
    2. We sell at 4, buy at 1, sell at 7, buy at 3, which results profit = 4 - 1 - 2 + 7 - 3 - 2 = 7 - 1 - 2 + (4 - 3 - 2).

    We can find the difference is (4 - 3 - 2).
    Then we use last_sell to store last sell price (4 when we visit 7), min2 to store the minimum price after last sell (3 when we visit 7), min1 to store the minimum price before last sell and after the sell before last sell.

        int maxProfit(vector<int>& prices, int fee) {
            int min1 = INT_MAX, min2 = INT_MAX, res = 0;
            int last_sell = INT_MAX;
            for (int i = 0; i < prices.size(); ++i) {
                min2 = min(min2, prices[i]);
                if (prices[i] - min2 > fee && (min1 == INT_MAX || last_sell - min2 > fee)) {    // new purchase
                    res += prices[i] - min2 - fee;
                    min1 = min2;
                    min2 = last_sell = prices[i];
                } else if (prices[i] > last_sell) { // update purchase
                    res += prices[i] - last_sell;
                    min2 = last_sell = prices[i];
                }
            }
            return res;
        }
    

Log in to reply
 

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