C++ DP solution with explanation


  • 0
    class Solution {
    public:
        int maxProfit(int k, vector<int>& prices) {
            if (k >= prices.size()/2) {
                int res = 0;
                for (int i = 1; i < prices.size(); ++i)
                    res += max(prices[i] - prices[i-1], 0);
                return res;
            }
            int n = k * 2 + 1;
            vector<int> dp(n, 0);
            for (int i = 1; i < n; i += 2) {
                dp[i] = INT_MIN;
            }
            for (int price : prices) {
                for (int i = 1; i < n; i++) {
                    dp[i] = max(dp[i], dp[i - 1] + (i&1 ? (-1 * price) : price));
                }
            }
            return dp[n - 1];
        }
    };
    

    if you have trouble to understand this solution, please read the following code for Best Time to Buy and Sell Stock |||. It is simple version of this DP solution.

    int maxProfit(vector<int>& prices) {
        //It's wrong if you choose the minimum price for buy2 , but you can maximize the left money.
        //
        int buy1 = INT_MIN, sale1 = 0, buy2 = INT_MIN, sale2 = 0;
        for(int i=0; i<prices.size(); i++){                      //the more money left, the happier you will be
            buy1 = max(buy1, -prices[i]);                        //left money after buy1
            sale1 = max(sale1, prices[i] + buy1);                //left money after sale1
            buy2 = max(buy2, sale1 - prices[i]);                 //left money after buy2
            sale2 = max(sale2, prices[i] + buy2);                //left money after sale2
        }
        return sale2;
    }
    

    I think the test case with k = 1000000000 does not necessary. It asks programer add

            if (k >= prices.size()/2) {
                int res = 0;
                for (int i = 1; i < prices.size(); ++i)
                    res += max(prices[i] - prices[i-1], 0);
                return res;
            }
    

    to rule out this case which alloc too much memory. But I do not think it is contribute anything for the algorithm.


Log in to reply
 

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