Leetcode 188 Solution

This article provides solution to leetcode question 188 (best-time-to-buy-and-sell-stock-iv).
Categories:
Tags:
Access this page by simply typing in "lcs 188" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv

Solution

class Solution {
    int maxProfit(vector<int>& prices) {
        int total = 0;
        
        for (int i = 1; i < prices.size(); i++)
        {
            if (prices[i] - prices[i - 1] > 0)
                total += prices[i] - prices[i - 1];
        }
        
        return total;
    }
    
public:
    int maxProfit(int k, vector<int>& prices) {
        if (prices.size() == 0)
            return 0;
        
        if (k >= prices.size())
            return maxProfit(prices);

        vector<int> dp1(k + 1);
        vector<int> dp2(k + 1);
        
        for (int i = 0; i < prices.size() - 1; i++)
        {
            int diff = prices[i + 1] - prices[i];

            for (int j = k; j >= 1; --j)
            {
                dp2[j] = max(dp2[j] + diff, dp1[j - 1] + max(diff, 0));
                dp1[j] = max(dp1[j], dp2[j]);
            }
        }
        
        return dp1[k];
    }
};