题目描述

给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。​

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

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

示例 1:

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

示例 2:

输入: prices = [1]
输出: 0

提示：

  • 1 <= prices.length <= 5000
  • 0 <= prices[i] <= 1000

代码实现

其实在完成买卖股票的最佳时机 IV后，基本上所有的股票类题目都可以用动态规划来解决了。而且思路都非常相似。

确定动态规划的阶段，就是以每天为一个阶段。确定每天的状态：不持有股票且还在冷冻期、不持有股票且不在冷冻期、持有股票。然后确定状态转移方程：

  • 不持有股票且还在冷冻期：只能由持有股票的状态转移过来(原来拥有过，当天卖出了)，也就是 newdp[0] = dp[2] + prices[i]
  • 不持有股票且不在冷冻期：可以由不持有股票且不在冷冻期的状态转移过来，也可以由不持有股票且还在冷冻期的状态转移过来，也就是 newdp[1] = max(dp[0], dp[1])
  • 持有股票：可以由不持有股票且不在冷冻期的状态转移过来（当天买入），也可以由持有股票的状态转移过来，也就是 newdp[2] = max(dp[2], dp[1]-prices[i])

比较简单，就不写动态转移方程了，直接编写代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func max(a, b int) int {
	if a > b {
		return a
	}

	return b
}

func maxProfit(prices []int) int {
	dp := []int{0, 0, -prices[0]} // 0: 不持有且冷冻 1: 不持有不冷冻 2: 持有

	for i := 1; i < len(prices); i++ {
		dp[0], dp[1], dp[2] = dp[2]+prices[i], max(dp[0], dp[1]), max(dp[2], dp[1]-prices[i])
	}

	return max(dp[0], dp[1])
}

这里需要注意更新 dp 数组的顺序，不能直接用 dp[0] = dp[2]+prices[i]，因为 dp[0] 的值会被覆盖掉，而 dp[2] 的值是需要用到上一天 dp[0] 的值的，所以需要用一个临时变量来保存 dp[0] 的值。当然也可以像上面的代码一样，用 Go 语言的多赋值语法来实现。

最后返回 max(dp[0], dp[1])，也就是不持有股票的最大利润。因为如果最后一天持有股票的话，说明没有卖出那肯定是不如不持有股票的利润高。

这里的时间复杂度是 O(n)，空间复杂度是 O(1)，因为只需要用到三个变量来保存状态。