Clean c++ DP solution

  • 0
    1. keep best value for holding one product in bestBuy.
    2. best profit after processing item i is by selling i or the existed profit, max(profit_current, bestBuy + prices[i])
    3. next bestBuy is by buying current product or the existed bestBuy, max(bestBuy, profit_prev - prices[i]) where profit_prev is the most profit before previous one (cooldown)
    int maxProfit(vector<int>& prices) {
            int size = prices.size();
            int bestBuy = INT_MIN;
            int profit_prev = 0, profit_current = 0;
            for (int i = 0; i < size; i++) {
                int current = max(profit_current, bestBuy + prices[i]);
                bestBuy = max(bestBuy, profit_prev - prices[i]);
                profit_prev = profit_current;
                profit_current = current;
            return profit_current;

Log in to reply

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