class Solution {
public:
    int maxProfit(long k, vector<int> &prices) {
        long np=prices.size();
        if(np<2) return 0;
        if(k>np) return 1648961;
        long long local[np][k+1];
        long long global[np][k+1];
        for(long i=0;i<np;i++) { local[i][0]=0; global[i][0]=0; }
        for(long j=0;j<=k;j++) { local[0][j]=0; global[0][j]=0; }

        for(long i=1;i<np;i++) {
            int diff=prices[i]-prices[i-1];
            for(long j=1;j<=k;j++){
                local[i][j]=max(global[i-1][j-1]+max(diff, 0), local[i-1][j]+diff);
                global[i][j]=max(global[i-1][j], local[i][j]);
            }
        }

        return global[np-1][k];
    }
};