题目描述

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

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。

示例 4：

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

提示：

  • 1 <= prices.length <= 3 * 104
  • 0 <= prices[i] <= 104

题目思路

一开始想着找出两个最大的递增子序列，然后求出两个子序列的差值之和。但发现不太好通过贪心算法来实现，因为只能操作两次并且不能同时进行。

其实前面做过类似的题目 121. 买卖股票的最佳时机 I，那是个简单题，就是在给定的价格数组中找出最大差值。所以这里就可以将问题拆分成两个子问题，分别计算前 i 天的最大利润和后 j 天的最大利润，然后将它们相加。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
func max(a, b int) int {
	if a > b {
		return a
	}

	return b
}

func maxSingleProfit(prices []int) int {
	if len(prices) <= 1 {
		return 0
	}

	maxProfit := 0
	for minPrice, i := prices[0], 1; i < len(prices); i++ {
		if prices[i] < minPrice {
			minPrice = prices[i]
		} else {
			maxProfit = max(maxProfit, prices[i]-minPrice)
		}
	}

	return maxProfit
}

func maxProfit(prices []int) int {
	maxProfit := 0
	for i := 0; i < len(prices)-1; i++ {
		maxProfit = max(maxProfit, maxSingleProfit(prices[:i+1])+maxSingleProfit(prices[i:]))
	}

	return maxProfit
}

这个方法的时间复杂度是 O(n^2)，空间复杂度是 O(1)，无法通过测试用例。因为在每次计算前 i 天的最大利润和后 j 天的最大利润的时候都要遍历一遍数组，所以时间复杂度是 O(n^2)。提交后也是发现超时了。继续思考，在基于分段计算的基础上，每次求解最大利润的时候，都存在一些重复计算。比如 3, 3, 5, 0, 0, 3, 1, 4：

  • 在计算前 4 天的最大利润的时候，已经计算过 3, 3, 5 的最大利润了，也知道 3, 3, 5 的最小值是 3，所以可以直接用 3 来计算后 4 天的最大利润即可。
  • 而计算后 4 天的最大利润的时候，可以先计算后 3 天的最大利润，然后再根据倒数第四天的价格来计算前 4 天的最大利润。

因此可以使用动态规划的方法来解决这个问题。动态规划的核心思想是将一个复杂的问题分解成简单的子问题，然后通过解决子问题来解决原问题。

  • 分别求出前 i 天的最大利润和后 j 天的最大利润，然后将它们相加，求出最大值。
  • 前 i 天的最大利润可以通过求前 i-1 天的最大利润和判断第 i 天卖出能否获得更大的利润来计算。
  • 后 j 天的最大利润可以通过求后 j+1 天的最大利润和判断第 j 天买入能否获得更大的利润来计算。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
func max(a, b int) int {
	if a > b {
		return a
	}

	return b
}

func maxProfit(prices []int) int {
	days := len(prices)
	dpFront := make([]int, days) // profit
	dpMin := prices[0]
	dpBack := make([]int, days) // profit
	dpMax := prices[days-1]

	for i, j := 1, days-2; i < days; i, j = i+1, j-1 {
		if profit := prices[i] - dpMin; profit < 0 {
			dpMin = prices[i]
			dpFront[i] = dpFront[i-1]
		} else {
			dpFront[i] = max(dpFront[i-1], profit)
		}

		if profit := dpMax - prices[j]; profit < 0 {
			dpMax = prices[j]
			dpBack[j] = dpBack[j+1]
		} else {
			dpBack[j] = max(dpBack[j+1], profit)
		}
	}

	maxProfit := 0
	for i := 1; i < days; i++ {
		maxProfit = max(maxProfit, dpFront[i]+dpBack[i])
	}

	return maxProfit
}

至此，时间复杂度是 O(n)，空间复杂度是 O(n)。可以通过所有测试用例。但是后来在看到LeetCode 的题解后，发现用了另一种动态规划的思路。说起来动态规划的思路难点也是这里，就是如何拆解问题并且如何定义状态。

乍一看官方题解的思路是有点复杂的，但其实仔细想如果这个问题改为 k 次交易的话，再用上面的思路就很难实现了。而官方题解的思路是可以扩展到 k 次交易的。每天的状态都会有 2k+1 种：

  • 买入 0 次，卖出 0 次
  • 买入 1 次，卖出 0 次
  • 买入 1 次，卖出 1 次
  • 买入 2 次，卖出 1 次
  • 买入 2 次，卖出 2 次
  • …
  • 买入 k 次，卖出 k-1 次
  • 买入 k 次，卖出 k 次

然后考虑状态转移：

  • 买入 1 次和卖出 0 次的状态可以从前一天买入 1 次和卖出 0 次的状态转移过来（具体来说，比较 “前一天买入 1 次、卖出 0 次的利润” 和 “前一天买入 0 次、卖出 0 次的利润”+“今天买入股票后的利润”，取较大值）；
  • 买入 1 次和卖出 1 次的状态可以通过买入 1 次和卖出 0 次的状态转移过来（也就是，比较 “前一天买入 1 次、卖出 1 次的利润” 和 “前一天买入 1 次、卖出 0 次的利润”+“今天卖出股票后的利润”，取较大值）；
  • 买入 2 次和卖出 1 次的状态可以通过买入 1 次和卖出 0 次的状态转移过来（也就是，比较 “前一天买入 2 次、卖出 1 次的利润” 和 “前一天买入 1 次、卖出 1 次的利润”+“今天卖出股票后的利润”，取较大值）；
  • 买入 2 次和卖出 2 次的状态可以通过买入 2 次和卖出 1 次的状态转移过来（也就是，比较 “前一天买入 2 次、卖出 2 次的利润” 和 “前一天买入 2 次、卖出 1 次的利润”+“今天卖出股票后的利润”，取较大值）；
  • …
  • 以此类推，直到买入 k 次和卖出 k 次的状态。

基于此就可以写出动态转移方程：

在第天，买入次，卖出次的最大利润，其中或

进行2次交易的动态规划

首先写出两次交易的动态规划代码：

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

	return b
}

func maxProfit(prices []int) int {
	s2 := 0

	for b1, s1, b2, i := -prices[0], 0, -prices[0], 1; i < len(prices); i++ {
		s2 = max(s2, b2+prices[i])
		b2 = max(b2, s1-prices[i])
		s1 = max(s1, b1+prices[i])
		b1 = max(b1, -prices[i])
	}

	return s2
}

上面的代码中 b1 表示已经进行 1 次买入和 0 次卖出，s1 表示已经进行 1 次买入和 1 次卖出，b2 表示已经进行 2 次买入和 1 次卖出，s2 表示已经进行 2 次买入和 2 次卖出。最终返回的结果就是 s2 的值。

遍历每天的股票价格，并根据价格更新 b1、s1、b2 和 s2 的值：

  • s2 比较 “前一天的 s2” 和 “前一天的b2 加上当天卖出股票后的收益 prices[i]”，取较大值；
  • b2 比较 “前一天的 b2” 和 “前一天的 s1 减去当天买入股票后的收益 prices[i]”，取较大值；
  • s1 比较 “前一天的 s1” 和 “前一天的 b1 加上当天卖出股票后的收益 prices[i]”，取较大值；
  • b1 比较 “前一天的 b1” 和 “前一天的 -prices[i]”，取较大值；
  • 最终返回 s2 的值。

这里需要两点：

  • b1 和 b2 的初始值都是是 -prices[0]，也就是在第一天买入股票的收益（b2 可以理解为在一天买入、卖出再买入的收益）；
  • s1 和 s2 的初始值都是 0，也就是在第一天不买入股票的收益（s2 可以理解为在一天买入、卖出再买入、卖出的收益）；

基于上面的思考，可以定义一个二维数组 dp[k+1][2]，dp[k][0] 表示买入 k 次而卖出 k-1 次的最大利润，dp[k][1] 表示买入 k 次而卖出 k 次的最大利润。这里可以理解为用数组来表示这天所有购买状态下的最大利润，数组的第一个下标用来表示买入的次数，数组的第二个下标用来表示最后一次买入的股票是否已经卖出。举例来说：

  • dp[0][0] 表示买入 0 次而卖出 0 次的最大利润；
  • dp[0][1] 表示买入 0 次而卖出 0 次的最大利润(第一个下标表示买入的次数，第二个下标表示最后一次买入的股票是否已经卖出，所以这里和 dp[0][0] 一样，值为 0)；
  • dp[1][0] 表示买入 1 次而卖出 0 次的最大利润；
  • dp[1][1] 表示买入 1 次而卖出 1 次的最大利润；
  • dp[2][0] 表示买入 2 次而卖出 1 次的最大利润；
  • dp[2][1] 表示买入 2 次而卖出 2 次的最大利润；

基于此可以修改代码为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const m int = 2

func maxProfit(prices []int) int {
	dp := make([][]int, m+1)
	for i := 0; i <= m; i++ {
		dp[i] = []int{-prices[0], 0}
	}
	dp[0][0] = 0

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

	return dp[m][1]
}

这里有 dp[0][0] 和 dp[0][1] 没有用到，所以即便 dp[0][0] 的值是错误的也不影响。避免引起误解，所以写了 dp[0][0] = 0 而已。

设置这个 dp 数组的长度为 m+1，一方面是为了代码可读性，另一方面也是为了方便后面扩展到 k 次交易的动态规划代码编写。

进行k次交易的动态规划

基于上面的代码，进一步修改就可以实现 k 次交易的动态规划了。dp 数组的大小为 k+1，然后要在循环中实现状态转移：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func max(a, b int) int {
	if a > b {
		return a
	}

	return b
}

const m int = 2

func maxProfit(prices []int) int {
	dp := make([][]int, m+1)
	for i := 0; i <= m; i++ {
		dp[i] = []int{-prices[0], 0}
	}

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

	return dp[m][1]
}

上面的代码需要注意的是：

  • dp[0][0] 的初始值应该是 0，但是在循环中并没有用到，所以忽略不管；
  • 第一个循环是遍历每天的股票价格，每次遍历都要更新 dp 数组的值；
  • 第二个循环是遍历 k 次交易的状态，这里是从 m 到 1 遍历的，因为在更新 dp[j][0] 的时候需要用到 dp[j-1][1] 的值，所以从后往前遍历更好理解；
  • 第二个循环无论是先计算 dp[j][1] 的值，还是先计算 dp[j][0] 的值其实对结果没有影响。因为在同一天中其实只需要买入或者卖出一次股票，哪怕多次买入或者卖出也是不会影响结果的，比如买入 3 次、卖出 2 次 和 买入 2 次、卖出 1 次的结果是一样的，再比如买入 2 次、卖出 2 次这个操作的收益是 0，所以假设先计算 dp[j][0] 的值，考虑一下两种情况：
    • dp[j][0] 的值如果是 dp[j-1][1]-prices[i]，也就是在第 i 天选择买入股票，那么 dp[j][1] 的值一定保持原来的 dp[j][1] 不变，因为当天卖出再买入是不会增加任何收益的（1, 2, 3 为例，购买两次: 1 买入、2 卖出后再买入、3 卖出，收益是 2，而购买一次: 1 买入、3 卖出，收益也是 2）；
    • dp[j][0] 的值如果是保持原来的 dp[j][0] 不变，那么 dp[j][1] 的值显然不受影响。
  • 同上面的论述，第二循环其实也可以从 1 到 m 遍历： 
    1
    2
    3
    4
    for j:= 1; j <= m; j++ {
    	dp[j][0] = max(dp[j][0], dp[j-1][1]-prices[i])
    	dp[j][1] = max(dp[j][1], dp[j][0]+prices[i])
    }

当然个人还是偏向于从后往前遍历，因为这样更容易理解。