LC188 Best Time to Buy and Sell

本题链接：Best Time to Buy and Sell Stock IV

本题标签：Dynamic Programming

本题难度：

英文题目 中文题目

---

方案1：

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if(prices.size() < 2)
            return 0;
        if(k < 1)
            return 0;
        
        int len = prices.size();
        if(k > len / 2) //Simple Case
        {
            int res = 0;
            for(int i = 1; i < len; ++i)
                res += max(prices[i] - prices[i-1], 0);
            return res;
        }
        
        vector<int> min_buy(k+1, prices[0]);
        vector<int> dp(k+1, 0);
        
        for(int i = 0; i < len; ++i)
        {
            for(int j = 1; j <= k; ++j)
            {
                min_buy[j] = min(min_buy[j], prices[i] - dp[j-1]);
                dp[j] = max(dp[j], prices[i] - min_buy[j]);
            }
        }
        
        return dp[k];
    }
};

时间复杂度：

空间复杂度：

---