$$\color{Red}{股票买卖 V 【状态机(图解加文字解析)】}$$

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

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

题目介绍

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

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

输入格式

第一行包含整数 N，表示数组长度。

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

输出格式

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

数据范围

1 ≤ N ≤ 10 ^ 5

输入样例：

5
1 2 3 0 2

输出样例：

3

样例解释：
对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]，第一笔交易可得利润 2-1 = 1，第二笔交易可得利润 2-0 = 2，共得利润 1+2 = 3。

思考

本题我们采取状态机模型，可以分为三个状态：
1.未持有股票2天及以上 （状态2）
2.未持有股票第1天 （状态1）
3.持有股票状态 （状态0）

                                              终点
     0                      终点                A     0
|----------|                 A                  |------------|
|          V     +w[i]       |        0         A            |
---------< 持仓 >------> 卖出第一天 >-----> 卖出二天及以上 <-|<-------<(起点)
           A            -w[i]                   V
           |------------------------------------|

为了初始化起点，我们需要把f[0][0], f[0][1]初始化为负无穷（代表无法转移到）
而起点f[0][2]初始化为0

java代码

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

public class Main {
    static int N = 100010, n, INF = 0x3f3f3f3f;
    static int[][] f = new int[N][3];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        String[] s1 = br.readLine().split(" ");
        f[0][0] = f[0][1] = -INF;
        f[0][2] = 0;
        for (int i = 1; i <= n; i++) {
            int w = Integer.parseInt(s1[i-1]);
            f[i][0] = Math.max(f[i-1][0], f[i-1][2] - w);
            f[i][1] = f[i-1][0] + w;
            f[i][2] = Math.max(f[i-1][1], f[i-1][2]);
        }
        //避免出现最开始的自转的边界情况，比如一次都不买
        System.out.println(Math.max(f[n][1], f[n][2]));
    }
}