Clean c++ DP solution


  • 1

    Idea is from previous version and extended to k.
    Running k rounds, each round store maximum profit for each item after processing from the beginning, in following two steps:

    1. calculate best value after one buy.
    2. calculate best value after one sell.
    int maxProfit(int k, vector<int>& prices) {
            int size = prices.size();
            if (k >= size / 2) {
                int result = 0;
                for (int i = 1; i < size; i++) {
                    if (prices[i] > prices[i - 1])
                        result += prices[i] - prices[i - 1];
                }
                return result;
            }
            int profit[size] = {0};
            for (int i = 0; i < k; i++) {
                int bestBuy = INT_MIN;
                int bestProfit = 0;
                for (int j = 0; j < size; j++) {
                    bestBuy = max(bestBuy, profit[j] - prices[j]);
                    bestProfit = max(bestProfit, bestBuy + prices[j]);
                    profit[j] = bestProfit;
                }
            }
            return profit[size - 1];
        }
    

Log in to reply
 

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