原题链接:
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii

解法1:

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
    f[i][j] 表示第i天 持有股票状态为j的 所持有的最大现金
    f[i][0] 不操作
    f[i][1] 第一次持有 
    f[i][2] 第一次不持有
    f[i][3] 第二次持有
    f[i][4] 第二次不持有
 */
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int [][] f = new int[n + 1][5];
        // 初始化
        // 第0天不操作 那就是0
        f[0][0] = 0;
        // 第1次持有 即第一次买入
        f[0][1] = -prices[0];
        // 第1次不持有 即买入后直接卖出
        f[0][2] = 0;
        // 第2次持有与不持有 与第1次逻辑相同
        f[0][3] = -prices[0];
        f[0][4] = 0;

        // 状态转移
        for(int i = 1; i < n ; i++){
            // 第i天不操作 那就是相当于 前一天的值
            f[i][0] = f[i - 1][0];
            // 第i天 第1次持有 那么只能是不操作 或者 从第i-1天不持有转移而来 那么只能买入
            f[i][1] = Math.max(f[i - 1][1],f[i - 1][0] - prices[i]);
            // 第i天 第1次不持有 那么只能是操作 或者 从第i-1天第1次持有转移而来 那么只能卖出
            f[i][2] = Math.max(f[i - 1][2],f[i - 1][1] + prices[i]);
            // f[i][3] f[i][4] 同理
            f[i][3] = Math.max(f[i - 1][3],f[i - 1][2] - prices[i]);
            f[i][4] = Math.max(f[i - 1][4],f[i - 1][3] + prices[i]);
        }

        // 最后一天都卖出 才肯能得到最大现金   
        return Math.max(f[n - 1][2],f[n - 1][4]);
    }
}