友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
123. 买卖股票的最佳时机 III
给定一个数组，它的第 `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 <= 105 -
0 <= prices[i] <= 105
思路分析
针对 一个方法团灭 6 道股票问题 - 最佳买卖股票时机含冷冻期 - 力扣（LeetCode） 这个解题框架，进行小试牛刀。
思考题：将表格改成变量时，还需要再思考思考。
-
一刷
-
二刷
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
/**
* Runtime: 2 ms, faster than 47.09% of Java online submissions for Best Time to Buy and Sell Stock III.
* Memory Usage: 42.5 MB, less than 7.32% of Java online submissions for Best Time to Buy and Sell Stock III.
*
* Copy from: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/solutions/8610/yi-ge-fang-fa-tuan-mie-6-dao-gu-piao-wen-ti-by-lab/[309. 买卖股票的最佳时机含冷冻期 - 一个方法团灭 6 道股票问题^]
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-28 20:14
*/
public int maxProfit(int[] prices) {
int dp10 = 0, dp11 = Integer.MIN_VALUE;
int dp20 = 0, dp21 = Integer.MIN_VALUE;
for (int i = 0; i < prices.length; i++) {
dp20 = Math.max(dp20, dp21 + prices[i]);
dp21 = Math.max(dp21, dp10 - prices[i]);
dp10 = Math.max(dp10, dp11 + prices[i]);
dp11 = Math.max(dp11, -prices[i]);
}
return dp20;
}
/**
* Runtime: 5 ms, faster than 22.10% of Java online submissions for Best Time to Buy and Sell Stock III.
* Memory Usage: 42.4 MB, less than 7.32% of Java online submissions for Best Time to Buy and Sell Stock III.
*/
public int maxProfitDpTable(int[] prices) {
if (Objects.isNull(prices) || prices.length == 0) {
return 0;
}
int maxK = 2;
int[][][] dp = new int[prices.length][maxK + 1][2];
for (int i = 0; i < prices.length; i++) {
for (int k = maxK; k >= 1; k--) {
if (i == 0) {
dp[i][k][0] = 0;
dp[i][k][1] = -prices[i];
continue;
}
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
}
}
return dp[prices.length - 1][maxK][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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-27 09:02:36
*/
public int maxProfit(int[] prices) {
// prices x
// 交易次数 y
// 买、卖、不动 买0，卖则为1
// dp[x][y][z]
// dp[x][y][0] = max{dp[x-1][y][0], dp[x-1][y][1]+price[x]}
// dp[x][y][1] = max{dp[x-1][y][1], dp[x-1][y-1][0]-price[x]}
int maxK = 2;
int[][][] dp = new int[prices.length][maxK + 1][2];
for (int x = 0; x < prices.length; x++) {
for (int y = maxK; y >= 1; y--) {
if (x == 0) {
dp[x][y][0] = 0;
dp[x][y][1] = -prices[x];
continue;
}
dp[x][y][0] = Math.max(dp[x - 1][y][0], dp[x - 1][y][1] + prices[x]);
dp[x][y][1] = Math.max(dp[x - 1][y][1], dp[x - 1][y - 1][0] - prices[x]);
}
}
return dp[prices.length - 1][maxK][0];
}