leetcode 188 Best Time to Buy and Sell Stock IV

https://www.cnblogs.com/grandyang/p/4295761.html

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if(prices.empty()) return 0;
        if(k>prices.size()) return helper(prices);
        vector<int> global(k+1,0),local(k+1,0);
        for(int i=0;i<prices.size()-1;++i) {
            int diff=prices[i+1]-prices[i];
            for(int j=k;j>=1;--j) {
                local[j]=max(global[j-1]+max(diff,0),local[j]+diff);
                global[j]=max(local[j],global[j]);
            }
        }
        return global[k];
    }
    int helper(vector<int>& prices) {
        int res=0;
        for(int i=1;i<prices.size();++i) {
            if(prices[i]>prices[i-1]) res+=(prices[i]-prices[i-1]);
        }
        return res;
    }
};