class Solution {
    public int maxProfit(int k, int[] prices) {
        if(prices.length < 2){
            return 0;
        }
        if (k > prices.length / 2)
            return func(prices);

        int[][] dp = new int[k + 1][prices.length];
        dp[0][0] = 0;

        for (int i = 1; i <= k; i++){
            int pftBuy = dp[i - 1][0] - prices[0];
            for (int j = 1; j <= prices.length - 1; j++){
                pftBuy = Math.max(pftBuy, dp[i - 1][j - 1] - prices[j]);
                dp[i][j] = Math.max(dp[i][j-1], pftBuy + prices[j]);
                
            }
        }

        return dp[k][prices.length - 1];
    }

    private int func(int[] prices) {
        int len = prices.length, profit = 0;
        for (int i = 1; i < len; i++)
            // as long as there is a price gap, we gain a profit.
            if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
        return profit;
    }
}