题解 | 买卖股票的最好时机(四)-时间复杂度O(n*k),空间复杂度O(k)

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] price = new int[n];
        for (int i = 0; i < n; i++) price[i] = in.nextInt();

        //每一天都会有k*2+1种状态，分别是初始化，第一次买入，第一次卖出，第二次买入，第二次卖出······
        int[] state = new int[k * 2 + 1];

        for (int i = 1; i < state.length; i += 2) // 初始化买入亏损
            state[i] = - price[0];

        for (int i = 1; i < n; i++) {
            state[0] = state[0];
            for (int j = 1; j < state.length; j++) {
                if (j % 2 == 1) { //表示要在当天买入
                    state[j] = Math.max(state[j], state[j - 1] - price[i]);
                } else { //表示要在当天卖出
                    state[j] = Math.max(state[j], state[j - 1] + price[i]);
                }
            }
        }
        
        int res = 0;
        for (int i = 2; i < state.length; i += 2)res = Math.max(res, state[i]);
        System.out.println(res);

    }
}