188. 买卖股票的最佳时机 IV

188. 买卖股票的最佳时机 IV

class Solution {
public:
    int maxInf(vector<int> &prices){
        int res=0;
        for(int i=1;i<prices.size();i++)
            res+=max(0,prices[i]-prices[i-1]);
        return res;
    }
    
    int maxProfit(int k, vector<int>& prices) {
        int n=prices.size();
        if(k<1||n<=1)return 0;
        if(k>n/2)return maxInf(prices);
        
        int dp[k+1][2];
        memset(dp,0x80,sizeof dp);
        dp[0][0]=dp[0][1]=0;
        // 0:无股票  1:有股票
        for(auto price:prices){
            for(int i=1;i<=k;i++){
                // 顺序不能反
                dp[i][1]=max(dp[i][1],dp[i-1][0]-price);   // 买
                dp[i][0]=max(dp[i][0],dp[i][1]+price);      // 卖
            }
        }
        return max(dp[k][0],dp[k][1]);
    }
};