算法分析

初始化：f[0][j][0] = 0, 其余-INF，因为在第0个股票一定是无货的，必定从这个位置开始转移才有效

注意：
这里状态机的过程，对于每个股票，要么就买，要么就卖，不能说是买了然后在同一个点直接卖掉，这样是不符合状态机模型的，因此对于上述转移方程可以会有人提出疑问。
为什么状态转移方程不能是下面代码，即卖的时候才算做了一次交易，原代码是买的时候才算一次交易

f[i][j][0] = max(f[i - 1][j - 1][1] + w[i], f[i - 1][j][0]);
f[i][j][1] = max(f[i - 1][j][0] - w[i], f[i - 1][j][1]);

终究要回归到状态转移的起点，第一支股票只有买，和不买这两个操作，一定不可能是卖和不卖的这两个操作，因此第一支股票如果买入时，必须按照一次交易处理。否则如果第一次股票如果买入时，不按一次交易处理，也就代表着第一支股票卖出才算一次交易，也就代表着在第一支股票卖出之前还买了一支股票，显然是矛盾的。

非状态机解法 LeetCode 188. 买卖股票的最佳时机 IV

时间复杂度 $O(nm)$

空间复杂度 $O(m)$

从$O(nm)$优化到$O(m)$

参考文献

算法提高课

Java 代码（空间优化前，在这里会gg的代码，c++不会）

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int N = 100010, M = 110, INF = 0x3f3f3f3f;
    static int n, m;
    static int[] w = new int[N];
    static int[][][] f = new int[N][M][2];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);

        String[] s2 = br.readLine().split(" ");
        for(int i = 1;i <= n;i ++) w[i] = Integer.parseInt(s2[i - 1]);

        for(int i = 0;i <= n;i ++)
            for(int j = 0;j <= m;j ++)
                Arrays.fill(f[i][j], -INF);
        for(int i = 0;i <= n;i ++) f[i][0][0] = 0;

        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= m;j ++)
            {
                f[i][j][0] = Math.max(f[i - 1][j][1] + w[i], f[i - 1][j][0]);
                f[i][j][1] = Math.max(f[i - 1][j - 1][0] - w[i], f[i - 1][j][1]);
            }

        int res = 0;
        for(int i = 1;i <= m;i ++) res = Math.max(res, f[n][i][0]);

        System.out.println(res);
    }
}

Java 代码（空间优化后）

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int N = 100010, M = 110, INF = 0x3f3f3f3f;
    static int n, m;
    static int[] w = new int[N];
    static int[][] f = new int[M][2];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);

        String[] s2 = br.readLine().split(" ");
        for(int i = 1;i <= n;i ++) w[i] = Integer.parseInt(s2[i - 1]);

        for(int j = 0;j <= m;j ++)
            Arrays.fill(f[j], -INF);

        f[0][0] = 0;

        for(int i = 1;i <= n;i ++)
            for(int j = m;j >= 1;j --)
            {
                f[j][0] = Math.max(f[j][1] + w[i], f[j][0]);
                f[j][1] = Math.max(f[j - 1][0] - w[i], f[j][1]);
            }

        int res = 0;
        for(int i = 1;i <= m;i ++) res = Math.max(res, f[i][0]);

        System.out.println(res);
    }
}