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

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

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

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

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

示例:

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

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

本题根据官方提示，是动态规划的思想。当天的收益与昨天的操作有关，让我们来找出状态转移方程。首先我们先考虑第一天的状态，在第一天有两种情况，(1) 我手上没有股票，就表示我没有买入，(2) 我手上有一只股票，表示我买入了一只股票，因为是第一天，我们不考虑冻结期的状态。

第 i 天一共有三种情况：

1. 我们当天手里持有一张股票。这张股票有两种可能性，第一种是我在i 天没有购入，这种状态下我们在i-1天持有一只股票；第二种情况就是在i 天购入的，那么如果在i 天购入的话，就说明在 i-1天没有持有股票且在第i-1天不处在冷冻期。
2. 我们当天没有持有股票，且处在冷冻期。这种状态下，说明在 i-1天的时候购入了一只股票。
3. 我们当天没有持有股票，且不处在冷冻期，这也有两种可能性。第一种是i-1 属于第二种情况，就是处于冷冻期；第二种是i-1属于第三种情况，没有进行任何操作。

下面我们把上述三种情况符号化，我们将第一种情况记为 statusOne，第二种情况记为 statusTwo，第三种情况记为 statusThree，：

1. 第一种情况的状态转移方程为：

$$statusOne = max(statusOne, statusThree - prices[i])$$

1. 第二种情况的状态转移方程为：

$$statusTwo = statusOne + prices[i]$$

1. 第三种情况的状态转移方程为：

$$statusThree = max(statusTwo, statusThree)$$

这里使用三个变量而不是整个数组，是因为第i天的状态只与第 i-1天的状态有关，这样做会进一步优化空间复杂度。最后，我们只需要返回 statusOne、 statusTwo和 statusThree三者中的最大值就可以了，考虑到最后一天还持有股票肯定不会是最大收益，所以只需要返回 statusTwo和statusThree中的较大值即可。

具体代码实现如下：

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

        //第一种情况是当天持有股票
        //因为是第一天，所以就是当天购买的股票，所以收益需要花费prices[0]
        int statusOne = -prices[0];
        int statusTwo = 0;
        int statusThree = 0;
        int temp1, temp2, temp3 = 0;
        for (int i = 1; i < len; i++) {
            //根据状态转移方程更新股票收益
            temp1 = Math.max(statusOne, statusThree - prices[i]);
            temp2 = statusOne + prices[i];
            temp3 = Math.max(statusTwo, statusThree);
            statusOne = temp1;
            statusTwo = temp2;
            statusThree = temp3;

            //这里不能这样写，因为这样写的话在一个循环里，statusOne更新过后的值会影响statusTwo的值
//            statusOne = Math.max(statusOne, statusThree - prices[i]);
//            statusTwo = statusOne + prices[i];
//            statusThree = Math.max(statusTwo, statusThree);
        }

        //因为在最后一天还持有股票没有意义，会减少收益
        //所以只考虑statusTwo和statusThree的情况
        return Math.max(statusTwo, statusThree);
    }
}