class Solution {
    public int maxProfit(int k, int[] prices) {
        int profit = 0;
        if (prices.length == 0) return profit;
        if (prices.length / 2 < k) {
            for (int i = 1; i < prices.length; i++) {
                profit += Math.max(0, prices[i] - prices[i - 1]);
            }
            return profit;
        }
        int[][] dp = new int[k + 1][prices.length + 1];
        // dp[i][j] = max(
        //     dp[i][j - 1],
        //     max(dp[i - 1][l] + prices[j] - prices[l])
        //         => prices[j] + max(dp[i - 1][l] - prices[l])
        // ), 0 <= l < j
        for (int i = 1; i <= k; i++) {
            int max = dp[i - 1][0] - prices[0];
            for (int j = 1; j <= prices.length; j++) {
                dp[i][j] = Math.max(dp[i][j - 1], prices[j - 1] + max);
                max = Math.max(max, dp[i - 1][j] - prices[j - 1]);
                profit = Math.max(profit, dp[i][j]);
            }
        }
        return profit;
    }
}