题目描述

给定一个整数数组,其中第 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 状态转换图

对于第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 算法执行例1

图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)

图3 算法执行例2

对于这个例子,我们仅讲解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/

pwrliang Algorithms, Dynamic Programming ,

Leave a Reply

Your email address will not be published. Required fields are marked *