LeetCode309-最佳买卖股票时机含冷冻期

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

中文链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

题目详述

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

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

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

示例:

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

题目详解

本题在 LeetCode122-买卖股票的最佳时机II 基础上增加了一个冷冻期，存在两个有效状态：持有股票和未持有股票，可以运用动态规划来解决。

  • sell[i] 表示第 i 天时未持有股票可获得的最大利润。
  • buy[i] 表示第 i 天时持有股票可获得的最大利润。
  • 对于 sell[i]，最大利润有两种可能，一是今天依旧不持股跟昨天状态一样；二是今天卖了股票，状态转移方程为 sell[i] = max{sell[i - 1], buy[i - 1] + prices[i]}。
  • 对于 buy[i]，最大利润有两种可能，一是今天持股跟昨天状态一样；二是前天卖了股票，今天买入股票。因为存在 cooldown 的原因，所以今天买股票要追溯到前天的状态，状态转移方程为 buy[i] = max{buy[i - 1], sell[i - 2]} - prices[i]。
  • 最终的结果为最后一天不持有股票的状态，即 sell[n - 1]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class LeetCode_00309 {

    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        int[] sell = new int[prices.length];
        int[] buy = new int[prices.length];
        sell[0] = 0;
        buy[0] = -prices[0];
        for (int i = 1; i < prices.length; ++i) {
            sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
            buy[i] = Math.max(buy[i - 1], (i >= 2 ? sell[i - 2] : 0) - prices[i]);
        }
        return sell[prices.length - 1];
    }
}

因为 sell[i] 只依赖于 sell[i - 1] 和 buy[i - 1]，buy[i] 只依赖于 buy[i - 1] 和 sell[i - 2]，可以压缩空间，将空间复杂度从 O(n) 降到 O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class LeetCode_00309 {

    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        int curSell = 0;
        int preSell = 0;
        int buy = -prices[0];
        for (int i = 1; i < prices.length; ++i) {
            int tmp = curSell;
            curSell = Math.max(curSell, buy + prices[i]);
            buy = Math.max(buy, preSell - prices[i]);
            preSell = tmp;
        }
        return curSell;
    }
}