309. 最佳买卖股票时机含冷冻期

题目描述

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格。

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

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

示例:

输入: [1,2,3,0,2] 输出: 3  解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

解法1

解法1使用到了有限状态机（FSM），在第i天我们的状态有3种，分别是hold（持股）、sold（抛售）和rest（休息）。第i天的hold状态可由第i-1天的hold状态（继续持有）和第i-1天的rest状态（买入股票）而来。第i天的rest状态可由第i-1天的rest状态（继续休息）和第i-1天的sold状态（冷冻期）而来。第i天的sold状态只能从第i-1天的hold状态而来（抛售股票）。我们在图1描述了这些状态。

对于第1天，sold状态是不合法的，因为我们还没有买进；对于hold和rest状态是合法的。题目要求计算最大利润，那么最后一天的最大利润只可能来自sold或者rest状态，而绝不可能来自于hold状态(因为我们手中持有股票)。

我们定义了3个长度为|prices|的数组来实现有限状态机，分别是hold、sold和rest。对于第1天，我们初始化hold[0] = -prices[0], sold[0] = -∞ （第1天抛售状态为不合法）, rest[0]。hold[i], sold[i]与rest[i]的物理意义分别是如果选择第i持股、抛售与休息能获得的最大利益。那么我们有：

hold[i] = max(hold[i-1], rest[i-1] – prices[i])
rest[i] = max(rest[i – 1], sold[i-1])
sold[i] = hold[i-1] + prices[i]

下面，我们举两个例子来解释算法执行过程。

图2中列举了算法执行过程，我们分别解释i=1（第二天）与i=4（第5天）的计算过程。

例1: (i = 1)

hold[1]：如果我们选择在第2天持有第1天第股票，那我们手中有-1元；如果我们选择在第2天买入股票，那么我们第1天只能休息，我们手中有-2元。hold[1] = max(hold[0], rest[0] – prices[1]) = max(-1, -2) = -1
sold[1]：我们在第2天卖出，则应该在第1天买入，有sold[1] = hold[0] + prices[1] = -1 + 2 = 1
rest[1]：如果我们选择第2天休息，那么前一天可以是休息状态，也可以是卖出状态带来的冷冻期。但是注意，第2天第的前一天是第1天，所以不可能取到卖出状态，这样我们初始化的sold[0] = -∞就使得max函数取不到sold[0]了。rest[1] = max(rest[0], sold[0]) = max(0, -∞) = 0

例1：(i = 4)

hold[4]：如果我们选择在第5天持有第4天第股票，我们手中有1元；如果我们选择在第5天买入股票，那第4天只能休息，我们手中有0元。hold[4] = max(hold[3], rest[3] – prices[4]) = max(1, 0) = 1
sold[4]：如果我们在第5天卖出，则第4天应该是持股状态，有sold[4] = hold[3] + prices[4] = 1 + 2 = 3
rest[4]：如果我们选择第5天休息，那么我们第4天可以卖出或休息。rest[4] = max(sold[3], rest[3]) = max(-1, 2) = 2

在这个例子中，我们选择最后一天（第5天）卖出能够获得最大利益3。

例2：(i = 4)

对于这个例子，我们仅讲解i=4（第5天）的计算过程

hold[4]：如果我们选择第5天持股，我们可以持有第4天的股票；或者第4天休息，第5天买入。有hold[4] = max(hold[3], rest[3] – prices[4]) = max(1, 5 – 3) = 2
sold[4]：如果我们选择第5天卖出，那么第4天应该持股。有sold[4] = hold[3] + prices[4] = 1 + 3 = 4
rest[4]：如果我们选择在第5天休息，那么可以从第4天休息状态而来，也可以因为第4天抛售产生的冷却而来。有rest[4] = max(rest[3], sold[3]) = max(5, -1) = 5

在这个例子中，我们选择最后一天（第5天）休息能够获得最大利益5。

分析完执行过程，我们开始编写代码吧。

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length <= 1)
            return 0;

        int[] hold = new int[prices.length];
        int[] sold = new int[prices.length];
        int[] rest = new int[prices.length];

        hold[0] = -prices[0];
        sold[0] = Integer.MIN_VALUE;

        for (int i = 1; i < prices.length; i++) {
            hold[i] = Math.max(hold[i - 1], rest[i - 1] - prices[i]);
            sold[i] = hold[i - 1] + prices[i];
            rest[i] = Math.max(sold[i - 1], rest[i - 1]);
        }

        return Math.max(rest[prices.length - 1], sold[prices.length - 1]);
    }
}

解法1 优化

从上面的代码可以看出，hold[i]、sold[i]与rest[i]仅依赖于i-1的值。因此我们可以定义hold[2], sold[2]与rest[2]，将[0]与[1]交替使用。

需要注意一点，因为数组索引是0与1交替使用的，那么最后一天落在0还是1的位置取决于天数是奇数还是偶数，因此我们要取索引为0与1的最大值。全部代码如下所示。

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length <= 1)
            return 0;

        int[] hold = new int[2];
        int[] sold = new int[2];
        int[] rest = new int[2];

        hold[0] = -prices[0];
        sold[0] = Integer.MIN_VALUE;

        for (int i = 1; i < prices.length; i++) {
            int prevIdx = (i - 1) % 2;
            int currIdx = i % 2;

            hold[currIdx] = Math.max(hold[prevIdx], rest[prevIdx] - prices[i]);
            sold[currIdx] = hold[prevIdx] + prices[i];
            rest[currIdx] = Math.max(sold[prevIdx], rest[prevIdx]);
        }

        return Math.max(Math.max(rest[0], rest[1]), Math.max(sold[0], sold[1]));
    }
}

参考：https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-309-best-time-to-buy-and-sell-stock-with-cooldown/

Liang' Blog