题目
You are given an array prices where prices[i] is the price of a given stock on the ith day.
Find the maximum profit you can achieve.
You may complete at most two transactions.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
例子
Example 1:
1
2
3
4Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
Example 2:
1
2
3
4Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
1
2
3Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
约束
1
21 <= prices.length <= 10^5
0 <= prices[i] <= 10^5
解题思路
我们每天可以做的事情：
（1）买入/卖出股票 持有不变
（2）一共最多可以买卖，共计 4 次。也就是题目中的 2 次完整的交易流程。
变量定义
transactionsLeft: 还能做几次交易。
- 无交易
1ans1 = solve(day + 1, transactionsLeft);
- 执行交易
1
2
3
4
5
6
7// 第一次，和第三次是买入
bool buy = (transactionsLeft % 2 == 0);
if(buy == true) {
ans2 = -prices[day] + solve(day + 1, transactionsLeft - 1);
}else{
ans2 = prices[day] + solve(day + 1, transactionsLeft - 1);
}
找到其中最好的，作为返回的结果。
递归终止条件
day >= prices.size || transactionsLeft <= 0
股票遍历结束，或者交易次数结束。
算法 java
思路
我们从递归，一步步来解决这个问题。
否则，永远都无法学会 DP。
当非常熟练的时候，可以考虑直接使用 DP。
递归
我们把所有的选择穷举，然后找出最大的结果。
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52 /**
* 递归算法，不考虑时间
*
* 1. 最多只能做 4 次交易。2次买入，2次卖出
* 2. 一天最多2种决策：
*
* 2.1 不做交易
* 2.2 做交易：买入/卖出
*
* 3. 时间在流逝
*
*
* @param prices 价格数组
* @return 结果
*/
public int maxProfit(int[] prices) {
return solve(prices, 0, 4);
}
/**
*
* @param prices 价格表
* @param day 第几天
* @param txTimeLeft 交易次数剩余
* @return 结果
*/
private int solve(int[] prices,
int day,
int txTimeLeft) {
// 终止条件
if(day >= prices.length
|| txTimeLeft <= 0) {
return 0;
}
//1. 策略1，不做交易
int profitNoTx = solve(prices, day+1, txTimeLeft);
//2. 策略2，进行交易
int profitTx = 0;
if(txTimeLeft % 2 == 0) {
//2.1 买入，钱-
profitTx = -prices[day] + solve(prices, day + 1, txTimeLeft-1);
} else {
//2.2 卖出，钱+
profitTx = prices[day] + solve(prices, day + 1, txTimeLeft-1);
}
//3. 返回最大的策略结果
return Math.max(profitNoTx, profitTx);
}
Memoization Solution
内存化记录每一次计算的结果，避免重复计算。
这里 mem 要初始化为 -1，避免默认值 0 的出现。
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90 /**
* 递归算法，不考虑时间
*
* 1. 最多只能做 4 次交易。2次买入，2次卖出
* 2. 一天最多2种决策：
*
* 2.1 不做交易
* 2.2 做交易：买入/卖出
*
* 3. 时间在流逝
*
*
* 优化思路：通过 DP 替代掉递归。
*
* 如果避免掉重复计算呢？
*
* https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
*
* @param prices 价格数组
* @return 结果
*/
public int maxProfit(int[] prices) {
// 行：prices.length
// 列：次数
int txTimeLeft = 4;
int[][] mem = new int[prices.length][txTimeLeft+1];
// 初始化为-1？，还是默认的 0 就可以
this.fillArrays(mem, -1);
return solve(prices, 0, txTimeLeft, mem);
}
private void fillArrays(int[][] mem, int initVal) {
int rows = mem.length;
int cols = mem[0].length;
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
mem[i][j] = initVal;
}
}
}
/**
*
* @param prices 价格表
* @param day 第几天
* @param txTimeLeft 交易次数剩余
* @param mem 内存
* @return 结果
*/
private int solve(int[] prices,
int day,
int txTimeLeft,
int[][] mem) {
// 终止条件
if(day >= prices.length
|| txTimeLeft <= 0) {
return 0;
}
// 从历史 mem 的结算结果中，直接获取结果
int ans = mem[day][txTimeLeft];
if(ans != -1) {
return ans;
}
//1. 策略1，不做交易
int profitNoTx = solve(prices, day+1, txTimeLeft, mem);
//2. 策略2，进行交易
int profitTx = 0;
if(txTimeLeft % 2 == 0) {
//2.1 买入，钱-
profitTx = -prices[day] + solve(prices, day + 1, txTimeLeft-1, mem);
} else {
//2.2 卖出，钱+
profitTx = prices[day] + solve(prices, day + 1, txTimeLeft-1, mem);
}
//3. 返回最大的策略结果
int maxProfit = Math.max(profitNoTx, profitTx);
// 返回之前，存储对应的结果
mem[day][txTimeLeft] = maxProfit;
return maxProfit;
}
改动点非常少：
（1）初始化一个 mem 数组，默认值为 -1
（2）递归逻辑调整
2.1 如果 mem 数组中已经计算过了，直接复用，避免重复计算
2.2 每次返回结果之前，记录一下对应的 mem 结果。
DP solution with O(N) space
Converting the recursive solution to iterative, Again exact same code just reverse the direction.
把递归改成迭代的算法实现。
迭代的逻辑其实就是 2 次迭代：
（1）迭代每一天
（2）每一天，迭代每一种交易策略
PS: 其实，从这里也可以看出 DP 的另一种实现方式。先把递归改成迭代，然后加入 mem。本质是一样的。
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67 /**
*
* 优化思路：通过 DP 替代掉递归。
*
* https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
*
* @param prices 价格数组
* @return 结果
*/
public int maxProfit(int[] prices) {
final int maxTxTime = 4;
int[][] dp = new int[prices.length+1][maxTxTime+1];
return solve(prices, dp, maxTxTime);
}
/**
* 解决
* @param prices 价格数组
* @param dp dp
* @param maxTxTime 最大交易次数
* @return 结果
*/
private int solve(int[] prices,
int[][] dp,
final int maxTxTime) {
// 迭代，而不是递归。
// 为什么天数，要从大=》小？
for(int day = prices.length; day >= 0; day--) {
// 内部循环交易次数
for(int txTime = 0; txTime <= maxTxTime; txTime++) {
int maxProfit = 0;
// 没有交易 / 第0天，收益默认为 0
if(txTime == 0
|| day == prices.length) {
maxProfit = 0;
} else {
//1. 策略1，不做交易
int profitNoTx = dp[day+1][txTime];
//2. 策略2，进行交易
int profitTx = 0;
//DP 中最重要的是 DP 的推导公式。
// 因为在前面递归的时候，我们使用的是直接 day 往下一步
// 换成迭代循环，这里需要把 day 从后往前，这样在计算 dp[day+1] 的时候，才能复用原来的值，不然都是初始化的值 -1
if(txTime % 2 == 0) {
//2.1 买入，钱-
profitTx = -prices[day] + dp[day+1][txTime-1];
} else {
//2.2 卖出，钱+
profitTx = prices[day] + dp[day+1][txTime-1];
}
//3. 返回最大的策略结果
maxProfit = Math.max(profitNoTx, profitTx);
}
// 存储对应的结果
dp[day][txTime] = maxProfit;
}
}
// 最后一个结果
return dp[0][maxTxTime];
}
DP solution with O(1) space
优化思路：空间这一块。因为在 dp 的递推公式中，我们只依赖一天前的数据，所以太多了也是浪费。
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76 /**
*
* 优化思路：通过 DP 替代掉递归。
*
* DP 的内存优化。
*
* Observation : For any day we just need the answers of the next day (day + 1) => Optimising it further to O(1) space
*
* 所以我们并不需要创建一个 dp[days][maxTx] 的数组，只需要一个 dp[2][maxTx] 的即可。
*
* https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
*
* @param prices 价格数组
* @return 结果
*/
public int maxProfit(int[] prices) {
final int maxTxTime = 4;
// 只需要保留 2 天，迭代也只依赖 2 天的数据。
int[][] dp = new int[2][maxTxTime+1];
return solve(prices, dp, maxTxTime);
}
/**
* 解决
*
* 把上一次涉及到 prices 日期的，全部通过 day % 2 替代。
* @param prices 价格数组
* @param dp dp
* @param maxTxTime 最大交易次数
* @return 结果
*/
private int solve(int[] prices,
int[][] dp,
final int maxTxTime) {
// 迭代，而不是递归。
// 为什么天数，要从大=》小？
for(int day = prices.length; day >= 0; day--) {
// 内部循环交易次数
for(int txTime = 0; txTime <= maxTxTime; txTime++) {
int maxProfit = 0;
// 没有交易 / 第0天，收益默认为 0
if(txTime == 0
|| day == prices.length) {
maxProfit = 0;
} else {
//1. 策略1，不做交易
int profitNoTx = dp[(day+1)%2][txTime];
//2. 策略2，进行交易
int profitTx = 0;
//DP 中最重要的是 DP 的推导公式。
// 因为在前面递归的时候，我们使用的是直接 day 往下一步
// 换成迭代循环，这里需要把 day 从后往前，这样在计算 dp[day+1] 的时候，才能复用原来的值，不然都是初始化的值 -1
if(txTime % 2 == 0) {
//2.1 买入，钱-
profitTx = -prices[day] + dp[(day+1) % 2][txTime-1];
} else {
//2.2 卖出，钱+
profitTx = prices[day] + dp[(day+1) % 2][txTime-1];
}
//3. 返回最大的策略结果
maxProfit = Math.max(profitNoTx, profitTx);
}
// 存储对应的结果
dp[day % 2][txTime] = maxProfit;
}
}
// 最后一个结果
return dp[0][maxTxTime];
}
然后所有的日期下标，调整为对应的 day % 2 即可。
性能
然而，上面的算法跑分为：
速度：40%
内存：50%
可恶，难道是可以剪枝吗？
问题所在
其实，两次交易，有更加简单的方式。
上面的 DP 很明显是更加通用的 K 次解法。
针对性解法思路
首先假设我们没有钱，所以 buy1 意味着我们要向别人借钱，我们要少借，所以我们必须使我们的余额尽可能多（因为这是负数）。
| sell1 表示我们决定卖出股票，卖出后我们有 price[i] 钱，我们必须归还我们欠的钱，所以我们有 price[i] - | buy1 | = prices[i ] + buy1，我们想要达到最大值。 |
buy2 意味着我们想买另一只股票，我们已经有 sell1 的钱，所以在买了 stock2 之后我们还有 buy2 = sell1 - price[i] 剩下的钱，我们想要更多的钱，所以我们把它设为 max
sell2 表示我们要卖出 stock2，卖出后我们可以得到 price[i] 的钱，而我们之前还有 buy2 的钱，所以 sell2 = buy2 + prices[i]，我们让这个最大值。
所以 sell2 是我们可以拥有的最多的钱。
实现
1
2
3
4
5
6
7
8
9
10
11public int maxProfit(int[] prices) {
int sell1 = 0, sell2 = 0, buy1 = Integer.MIN_VALUE, buy2 = Integer.MIN_VALUE;
for (int i = 0; i < prices.length; i++) {
//
buy1 = Math.max(buy1, -prices[i]);
sell1 = Math.max(sell1, buy1 + prices[i]);
buy2 = Math.max(buy2, sell1 - prices[i]);
sell2 = Math.max(sell2, buy2 + prices[i]);
}
return sell2;
}
If you still do not understand, see below.
buy1 and *sell1 *are for the first transaction.
buy2 and *sell2 *are for the second transaction.
变量背后的逻辑
要了解隐藏的逻辑，您必须了解这 4 个变量代表什么。
sell2：最终利润。
buy2：如果您不是在第 i 天（第 2 笔交易）之后买入股票，那么迄今为止的最佳利润。
sell1：如果您不是在第 i 天（第一次交易）之后卖出股票，则目前为止的最佳利润。
buy1：买入股票的最低价格。
buy1 和 sell1 之间的逻辑非常简单。 您需要做的只是找到几天后买卖的最低价格。
当然，即使你以较低的价格买入股票，如果利润没有比以前大，sell1 也不会更新。
假设您在第 a 天卖出股票以获得第一笔交易的最大利润，该笔交易存储在 sell1 中。
诀窍来了。 假设您在第 b 天找到更好的交易，sell1 得到更新。
所以你有 2 个选择 buy2：
不更新 buy2，你仍然在 a 天卖掉你的股票。 没有改变。
用新的 sell1 更新 buy2，这意味着您在第 b 天卖出股票。
buy2 = sell1 - price[i] 表示您在第 b 天卖出股票并在第 i 天买入。 而且Day i绝对不会早于Day b，这就是隐藏的逻辑。
PS: 不得不说，这个思路很强。
参考资料
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/solutions/39615/my-explanation-for-o-n-solution/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/solutions/1523723/c-four-solutions-recursion-memoization-dp-with-o-n-space-dp-with-o-1-space/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/solutions/135704/detail-explanation-of-dp-solution/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/solutions/2818819/recursion-with-memoization-simple-java-solution-dynamic-programing/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/solutions/1523723/c-four-solutions-recursion-memoization-dp-with-o-n-space-dp-with-o-1-space/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/solutions/2743789/c-full-solution-from-brute-force-to-optimized-dp-clean-code-with-commented-code/
