$$\color{Red}{股票买卖 IV【状态机(三维朴素AND二维优化)】}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

给定一个长度为 N 的数组，数组中的第 i 个数字表示一个给定股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润，你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。一次买入卖出合为一笔交易。

输入格式

第一行包含整数 N 和 k，表示数组的长度以及你可以完成的最大交易笔数。

第二行包含 N 个不超过 10000 的正整数，表示完整的数组。

输出格式

输出一个整数，表示最大利润。

数据范围

1 ≤ N ≤ 10 ^ 5

1 ≤ k ≤ 100

输入样例1：

3 2
2 4 1

输出样例1：

8
24

输入样例2：

6 2
3 2 6 5 0 3

输出样例2：

7

样例解释：
样例1：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

样例2：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。共计利润 4+3 = 7.

思考

这里首先要明确，一次买入卖出合为一笔交易（题目规定），同时我们每次买入前必须卖出当前持有的所有股票。
我们以状态机模型来规定f[i][j][k]代表，正在进行第j次交易，且到达第i天，而k的0或1表示当前是否持有股票。
那么就有两种状态，即k为0的无股票状态，和k为1的持有股票状态；
状态转移可以有如下情况：
购入 0 - > 1 f[i][j][1] = f[i-1][j-1][0] - w[i]
持仓 1 - > 1 f[i][j][1] = f[i-1][j][1]
零仓 0 - > 0 f[i][j][0] = f[i-1][j][0]
卖空 1 - > 0 f[i][j][0] = f[i-1][j][1] + w[i]

根据题意，也就是想要完成一次新交易的开始（即从j-1到达j）需要由f[i-1][j-1][0] - w[i]进行转移才能达成j的增加。其他情况的状态转移都是还处于j-1交易状态。

java代码三维朴素，会TLE

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, n, k;
    static int[] w = new int[N];
    static int[][][] f = new int[N][M][2];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        k = 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<= k; j++)
                Arrays.fill(f[i][j], -0x3f3f3f3f);
        //把所有天数未持有股票的情况置为价值0，因为没有买入
        for(int i = 0; i <= n; i++) f[i][0][0] = 0;
        //然后将所有一次都不交易,却有货的情况初始化为负无穷
        //f[i][0][1] = -INF;//上面已经把这里初始化过了

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

Java二维优化，因为用到了i-1维度更小的j，为了防止污染需要倒序

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, n, k;
    static int[] w = new int[N];
    static int[][] f = new int[M][2];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        k = 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 <= k; i++)
                Arrays.fill(f[i], -0x3f3f3f3f);
        //把所有天数未持有股票的情况置为价值0，因为没有买入
        f[0][0] = 0;
        //然后将所有一次都不交易,却有货的情况初始化为负无穷
        //f[0][1] = -0x3f3f3f3f;//上面已经把这里初始化过了

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