6-liner O(1) space with explanation


  • 0

    For each day, the actions one can take are buy, sell or hold. Obviously, hold does not change the profit, so let's not classify it as an action. It is critical to define the proper state variables.

    For each day i, define:

    • buy[i]: maximum profit at end of day i with last action as buy;
    • sell[i]: maximum profit at end of day i with last action as sell.

    Note:

    • The last action up to day i might happen on or before day i.
    • If we want to get the max overall profit, the last action must be a sell.

    So we can get the straightforward state transfer equations:

    • buy[i] = max(buy[i-1], sell[i-1] - price[i] - fee)
    • sell[i] = max(sell[i-1], buy[i-1] + price[i])

    Note: (buy[i], sell[i]) only depends on previous (buy[i-1], sell[i-1]), so we can derive the O(1) solution below.

        int maxProfit(vector<int>& prices, int fee) {
            int buy = INT_MIN, sell = 0;
            for (int p : prices) {
                int last_buy = buy;
                buy = max(buy, sell - p - fee); // pay fee at buy
                sell = max(sell, last_buy + p);
            }
            return sell;
        }
    

Log in to reply
 

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