[188] 买卖股票的最佳时机 IV

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if(prices.size() <= 1 || k <1){
            return 0;
        }
        int length = prices.size();
        if (k >= length / 2) {
            return maxProfit(prices);
        }
        vector<vector<int> > dp(k+1, vector<int>(2, 0));
        for(int i = 0; i<=k; i++){
            dp[i][0] = 0;
            dp[i][1] = -prices[0];
        }
        for(int i =0 ; i<prices.size(); i++){
            for(int j = k; j> 0; j--){
                dp[j][0] = max(dp[j][0], dp[j][1] + prices[i]);
                dp[j][1] = max(dp[j][1], dp[j-1][0] - prices[i]);
            }
        }
        return dp[k][0];
    }
    int maxProfit(vector<int>& prices) {
        if(prices.size() <= 0){
            return 0;
        }
        int current_0;
        int current_1;
        int pre_0 = 0;
        int pre_1 = -1e9;
        for(int i =0 ; i<prices.size(); i++){
            current_0 = max(pre_0, pre_1 + prices[i]);
            current_1 = max(pre_1, pre_0 - prices[i]);
            pre_0 = current_0;
            pre_1 = current_1;
        }
        return current_0;
    }
};