import java.util.Arrays;

public class L0188 {
    public static void main(String[] args) throws Exception {
        int k = 2;
        int[] prices = { 2, 4, 1 };

        System.out.print(maxProfit(k, prices));
    }

    public static int maxProfit(int k, int[] prices) {

        if (prices.length == 0) {
            return 0;
        }

        int num = prices.length;
        int[][] buy = new int[num][k + 1]; // 对于第j次选择在第i天买入
        int[][] sell = new int[num][k + 1];// 对于第j次选择在第i天卖出

        int i, j;
        for (i = 0; i <= k; ++i) {
            buy[0][i] = -prices[0];// 第i次选择在第0天买入，此时有的钱为第0天前的负数；
            sell[0][i] = 0;// 第i次选择在第0天卖出，此时赚的钱为0；
        }

        for (i = 1; i < num; ++i) {
            buy[i][0] = Math.max(buy[i - 1][0], sell[i - 1][0] - prices[i]); // 第0次选择在第i天买，max{第0次在i-1天买，
                                                                             // 第0次在第i-1天处于卖出状态减去第i天的钱}
            for (j = 1; j <= k; ++j) {
                buy[i][j] = Math.max(buy[i - 1][j], sell[i - 1][j] - prices[i]);
                sell[i][j] = Math.max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]);
            }
        }
        return Arrays.stream(sell[num - 1]).max().getAsInt();
    }
}