mirror of
https://github.com/youngyangyang04/leetcode-master.git
synced 2026-02-02 18:39:09 +08:00
566 lines
18 KiB
Markdown
Executable File
566 lines
18 KiB
Markdown
Executable File
* [做项目（多个C++、Java、Go、测开、前端项目）](https://www.programmercarl.com/other/kstar.html)
|
||
* [刷算法（两个月高强度学算法）](https://www.programmercarl.com/xunlian/xunlianying.html)
|
||
* [背八股（40天挑战高频面试题）](https://www.programmercarl.com/xunlian/bagu.html)
|
||
|
||
# 123.买卖股票的最佳时机III
|
||
|
||
[力扣题目链接](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-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 <= 10^5
|
||
* 0 <= prices[i] <= 10^5
|
||
|
||
## 算法公开课
|
||
|
||
**[《代码随想录》算法视频公开课](https://programmercarl.com/other/gongkaike.html)：[动态规划，股票至多买卖两次，怎么求？ | LeetCode：123.买卖股票最佳时机III](https://www.bilibili.com/video/BV1WG411K7AR)，相信结合视频再看本篇题解，更有助于大家对本题的理解**。
|
||
|
||
|
||
## 思路
|
||
|
||
|
||
这道题目相对 [121.买卖股票的最佳时机](https://programmercarl.com/0121.买卖股票的最佳时机.html) 和 [122.买卖股票的最佳时机II](https://programmercarl.com/0122.买卖股票的最佳时机II.html) 难了不少。
|
||
|
||
关键在于至多买卖两次，这意味着可以买卖一次，可以买卖两次，也可以不买卖。
|
||
|
||
接来下我用动态规划五部曲详细分析一下：
|
||
|
||
1. 确定dp数组以及下标的含义
|
||
|
||
一天一共就有五个状态，
|
||
|
||
0. 没有操作 （其实我们也可以不设置这个状态）
|
||
1. 第一次持有股票
|
||
2. 第一次不持有股票
|
||
3. 第二次持有股票
|
||
4. 第二次不持有股票
|
||
|
||
dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金。
|
||
|
||
需要注意：dp[i][1]，**表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票，这是很多同学容易陷入的误区**。
|
||
|
||
例如 dp[i][1] ，并不是说 第i天一定买入股票，有可能 第 i-1天 就买入了，那么 dp[i][1] 延续买入股票的这个状态。
|
||
|
||
2. 确定递推公式
|
||
|
||
|
||
达到dp[i][1]状态，有两个具体操作：
|
||
|
||
* 操作一：第i天买入股票了，那么dp[i][1] = dp[i-1][0] - prices[i]
|
||
* 操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][1]
|
||
|
||
那么dp[i][1]究竟选 dp[i-1][0] - prices[i]，还是dp[i - 1][1]呢？
|
||
|
||
一定是选最大的，所以 dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1]);
|
||
|
||
同理dp[i][2]也有两个操作：
|
||
|
||
* 操作一：第i天卖出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]
|
||
* 操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2] = dp[i - 1][2]
|
||
|
||
所以dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])
|
||
|
||
同理可推出剩下状态部分：
|
||
|
||
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
|
||
|
||
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
|
||
|
||
|
||
3. dp数组如何初始化
|
||
|
||
第0天没有操作，这个最容易想到，就是0，即：dp[0][0] = 0;
|
||
|
||
第0天做第一次买入的操作，dp[0][1] = -prices[0];
|
||
|
||
第0天做第一次卖出的操作，这个初始值应该是多少呢？
|
||
|
||
此时还没有买入，怎么就卖出呢？ 其实大家可以理解当天买入，当天卖出，所以dp[0][2] = 0;
|
||
|
||
第0天第二次买入操作，初始值应该是多少呢？应该不少同学疑惑，第一次还没买入呢，怎么初始化第二次买入呢？
|
||
|
||
第二次买入依赖于第一次卖出的状态，其实相当于第0天第一次买入了，第一次卖出了，然后再买入一次（第二次买入），那么现在手头上没有现金，只要买入，现金就做相应的减少。
|
||
|
||
所以第二次买入操作，初始化为：dp[0][3] = -prices[0];
|
||
|
||
同理第二次卖出初始化dp[0][4] = 0;
|
||
|
||
4. 确定遍历顺序
|
||
|
||
从递归公式其实已经可以看出，一定是从前向后遍历，因为dp[i]，依靠dp[i - 1]的数值。
|
||
|
||
5. 举例推导dp数组
|
||
|
||
以输入[1,2,3,4,5]为例
|
||
|
||
|
||
|
||
|
||
大家可以看到红色框为最后两次卖出的状态。
|
||
|
||
现在最大的时候一定是卖出的状态，而两次卖出的状态现金最大一定是最后一次卖出。如果想不明白的录友也可以这么理解：如果第一次卖出已经是最大值了，那么我们可以在当天立刻买入再立刻卖出。所以dp[4][4]已经包含了dp[4][2]的情况。也就是说第二次卖出手里所剩的钱一定是最多的。
|
||
|
||
所以最终最大利润是dp[4][4]
|
||
|
||
以上五部都分析完了，不难写出如下代码：
|
||
|
||
```CPP
|
||
// 版本一
|
||
class Solution {
|
||
public:
|
||
int maxProfit(vector<int>& prices) {
|
||
if (prices.size() == 0) return 0;
|
||
vector<vector<int>> dp(prices.size(), vector<int>(5, 0));
|
||
dp[0][1] = -prices[0];
|
||
dp[0][3] = -prices[0];
|
||
for (int i = 1; i < prices.size(); i++) {
|
||
dp[i][0] = dp[i - 1][0];
|
||
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
|
||
dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
|
||
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
|
||
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
|
||
}
|
||
return dp[prices.size() - 1][4];
|
||
}
|
||
};
|
||
```
|
||
|
||
* 时间复杂度：O(n)
|
||
* 空间复杂度：O(n × 5)
|
||
|
||
当然，大家可以看到力扣官方题解里的一种优化空间写法，我这里给出对应的C++版本：
|
||
|
||
```CPP
|
||
// 版本二
|
||
class Solution {
|
||
public:
|
||
int maxProfit(vector<int>& prices) {
|
||
if (prices.size() == 0) return 0;
|
||
vector<int> dp(5, 0);
|
||
dp[1] = -prices[0];
|
||
dp[3] = -prices[0];
|
||
for (int i = 1; i < prices.size(); i++) {
|
||
dp[1] = max(dp[1], dp[0] - prices[i]);
|
||
dp[2] = max(dp[2], dp[1] + prices[i]);
|
||
dp[3] = max(dp[3], dp[2] - prices[i]);
|
||
dp[4] = max(dp[4], dp[3] + prices[i]);
|
||
}
|
||
return dp[4];
|
||
}
|
||
};
|
||
```
|
||
|
||
* 时间复杂度：O(n)
|
||
* 空间复杂度：O(1)
|
||
|
||
大家会发现dp[2]利用的是当天的dp[1]。 但结果也是对的。
|
||
|
||
我来简单解释一下：
|
||
|
||
dp[1] = max(dp[1], dp[0] - prices[i]); 如果dp[1]取dp[1]，即保持买入股票的状态，那么 dp[2] = max(dp[2], dp[1] + prices[i]);中dp[1] + prices[i] 就是今天卖出。
|
||
|
||
如果dp[1]取dp[0] - prices[i]，今天买入股票，那么dp[2] = max(dp[2], dp[1] + prices[i]);中的dp[1] + prices[i]相当于是今天再卖出股票，一买一卖收益为0，对所得现金没有影响。相当于今天买入股票又卖出股票，等于没有操作，保持昨天卖出股票的状态了。
|
||
|
||
**这种写法看上去简单，其实思路很绕，不建议大家这么写，这么思考，很容易把自己绕进去！**
|
||
|
||
对于本题，把版本一的写法研究明白，足以！
|
||
|
||
## 拓展
|
||
|
||
其实我们可以不设置，‘0. 没有操作’ 这个状态，因为没有操作，手上的现金自然就是0， 正如我们在 [121.买卖股票的最佳时机](https://programmercarl.com/0121.买卖股票的最佳时机.html) 和 [122.买卖股票的最佳时机II](https://programmercarl.com/0122.买卖股票的最佳时机II.html) 也没有设置这一状态是一样的。
|
||
|
||
代码如下：
|
||
|
||
``` CPP
|
||
// 版本三
|
||
class Solution {
|
||
public:
|
||
int maxProfit(vector<int>& prices) {
|
||
if (prices.size() == 0) return 0;
|
||
vector<vector<int>> dp(prices.size(), vector<int>(5, 0));
|
||
dp[0][1] = -prices[0];
|
||
dp[0][3] = -prices[0];
|
||
for (int i = 1; i < prices.size(); i++) {
|
||
dp[i][1] = max(dp[i - 1][1], 0 - prices[i]);
|
||
dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
|
||
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
|
||
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
|
||
}
|
||
return dp[prices.size() - 1][4];
|
||
}
|
||
};
|
||
```
|
||
|
||
## 其他语言版本
|
||
|
||
### Java:
|
||
|
||
```java
|
||
// 版本一
|
||
class Solution {
|
||
public int maxProfit(int[] prices) {
|
||
int len = prices.length;
|
||
// 边界判断, 题目中 length >= 1, 所以可省去
|
||
if (prices.length == 0) return 0;
|
||
|
||
/*
|
||
* 定义 5 种状态:
|
||
* 0: 没有操作, 1: 第一次买入, 2: 第一次卖出, 3: 第二次买入, 4: 第二次卖出
|
||
*/
|
||
int[][] dp = new int[len][5];
|
||
dp[0][1] = -prices[0];
|
||
// 初始化第二次买入的状态是确保 最后结果是最多两次买卖的最大利润
|
||
dp[0][3] = -prices[0];
|
||
|
||
for (int i = 1; i < len; i++) {
|
||
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
|
||
dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
|
||
dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
|
||
dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
|
||
}
|
||
|
||
return dp[len - 1][4];
|
||
}
|
||
}
|
||
|
||
// 版本二: 空间优化
|
||
class Solution {
|
||
public int maxProfit(int[] prices) {
|
||
int[] dp = new int[4];
|
||
// 存储两次交易的状态就行了
|
||
// dp[0]代表第一次交易的买入
|
||
dp[0] = -prices[0];
|
||
// dp[1]代表第一次交易的卖出
|
||
dp[1] = 0;
|
||
// dp[2]代表第二次交易的买入
|
||
dp[2] = -prices[0];
|
||
// dp[3]代表第二次交易的卖出
|
||
dp[3] = 0;
|
||
for(int i = 1; i <= prices.length; i++){
|
||
// 要么保持不变，要么没有就买，有了就卖
|
||
dp[0] = Math.max(dp[0], -prices[i-1]);
|
||
dp[1] = Math.max(dp[1], dp[0]+prices[i-1]);
|
||
// 这已经是第二次交易了，所以得加上前一次交易卖出去的收获
|
||
dp[2] = Math.max(dp[2], dp[1]-prices[i-1]);
|
||
dp[3] = Math.max(dp[3], dp[2]+ prices[i-1]);
|
||
}
|
||
return dp[3];
|
||
}
|
||
}
|
||
```
|
||
|
||
### Python:
|
||
|
||
> 版本一：
|
||
```python
|
||
class Solution:
|
||
def maxProfit(self, prices: List[int]) -> int:
|
||
if len(prices) == 0:
|
||
return 0
|
||
dp = [[0] * 5 for _ in range(len(prices))]
|
||
dp[0][1] = -prices[0]
|
||
dp[0][3] = -prices[0]
|
||
for i in range(1, len(prices)):
|
||
dp[i][0] = dp[i-1][0]
|
||
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
|
||
dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i])
|
||
dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i])
|
||
dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i])
|
||
return dp[-1][4]
|
||
```
|
||
|
||
> 版本二：
|
||
```python
|
||
class Solution:
|
||
def maxProfit(self, prices: List[int]) -> int:
|
||
if len(prices) == 0:
|
||
return 0
|
||
dp = [0] * 5
|
||
dp[1] = -prices[0]
|
||
dp[3] = -prices[0]
|
||
for i in range(1, len(prices)):
|
||
dp[1] = max(dp[1], dp[0] - prices[i])
|
||
dp[2] = max(dp[2], dp[1] + prices[i])
|
||
dp[3] = max(dp[3], dp[2] - prices[i])
|
||
dp[4] = max(dp[4], dp[3] + prices[i])
|
||
return dp[4]
|
||
```
|
||
|
||
### Go:
|
||
|
||
> 版本一
|
||
|
||
```go
|
||
func maxProfit(prices []int) int {
|
||
dp := make([][]int, len(prices))
|
||
for i := 0; i < len(prices); i++ {
|
||
dp[i] = make([]int, 5)
|
||
}
|
||
dp[0][0] = 0
|
||
dp[0][1] = -prices[0]
|
||
dp[0][2] = 0
|
||
dp[0][3] = -prices[0]
|
||
dp[0][4] = 0
|
||
for i := 1; i < len(prices); i++ {
|
||
dp[i][0] = dp[i-1][0]
|
||
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
|
||
dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i])
|
||
dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i])
|
||
dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i])
|
||
}
|
||
return dp[len(prices)-1][4]
|
||
}
|
||
func max(a, b int) int {
|
||
if a > b {
|
||
return a
|
||
}
|
||
return b
|
||
}
|
||
```
|
||
|
||
> 版本二
|
||
|
||
```go
|
||
func maxProfit(prices []int) int {
|
||
if len(prices) == 0 {
|
||
return 0
|
||
}
|
||
dp := make([]int, 5)
|
||
dp[1] = -prices[0]
|
||
dp[3] = -prices[0]
|
||
for i := 1; i < len(prices); i++ {
|
||
dp[1] = max(dp[1], dp[0] - prices[i])
|
||
dp[2] = max(dp[2], dp[1] + prices[i])
|
||
dp[3] = max(dp[3], dp[2] - prices[i])
|
||
dp[4] = max(dp[4], dp[3] + prices[i])
|
||
}
|
||
return dp[4]
|
||
}
|
||
|
||
func max(x, y int) int {
|
||
if x > y {
|
||
return x
|
||
}
|
||
return y
|
||
}
|
||
```
|
||
|
||
> 版本三
|
||
|
||
```go
|
||
func maxProfit(prices []int) int {
|
||
if len(prices) == 0 {
|
||
return 0
|
||
}
|
||
dp := make([][5]int, len(prices))
|
||
dp[0][1] = -prices[0]
|
||
dp[0][3] = -prices[0]
|
||
for i := 1; i < len(prices); i++ {
|
||
dp[i][1] = max(dp[i-1][1], 0 - prices[i])
|
||
dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i])
|
||
dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i])
|
||
dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i])
|
||
}
|
||
return dp[len(prices)-1][4]
|
||
}
|
||
|
||
func max(x, y int) int {
|
||
if x > y {
|
||
return x
|
||
}
|
||
return y
|
||
}
|
||
```
|
||
|
||
> 版本四：一维 dp 易懂版本
|
||
|
||
```go
|
||
func maxProfit(prices []int) int {
|
||
dp := make([]int, 4)
|
||
dp[0] = -prices[0]
|
||
dp[2] = -prices[0]
|
||
|
||
for _, price := range prices[1:] {
|
||
dc := slices.Clone(dp) // 这句话是关键，把前一天的 dp 状态保存下来，防止被覆盖掉，后面只用它，不用 dp，逻辑简单易懂
|
||
dp[0] = max(dc[0], -price)
|
||
dp[1] = max(dc[1], dc[0] + price)
|
||
dp[2] = max(dc[2], dc[1] - price)
|
||
dp[3] = max(dc[3], dc[2] + price)
|
||
}
|
||
|
||
return dp[3]
|
||
}
|
||
```
|
||
|
||
### JavaScript:
|
||
|
||
> 版本一：
|
||
|
||
```javascript
|
||
const maxProfit = prices => {
|
||
const len = prices.length;
|
||
const dp = new Array(len).fill(0).map(x => new Array(5).fill(0));
|
||
dp[0][1] = -prices[0];
|
||
dp[0][3] = -prices[0];
|
||
for (let i = 1; i < len; i++) {
|
||
dp[i][0] = dp[i - 1][0];
|
||
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
|
||
dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
|
||
dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
|
||
dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
|
||
}
|
||
return dp[len - 1][4];
|
||
};
|
||
```
|
||
|
||
> 版本二：
|
||
|
||
```javascript
|
||
const maxProfit = prices => {
|
||
const len = prices.length;
|
||
const dp = new Array(5).fill(0);
|
||
dp[1] = -prices[0];
|
||
dp[3] = -prices[0];
|
||
for (let i = 1; i < len; i++) {
|
||
dp[1] = Math.max(dp[1], dp[0] - prices[i]);
|
||
dp[2] = Math.max(dp[2], dp[1] + prices[i]);
|
||
dp[3] = Math.max(dp[3], dp[2] - prices[i]);
|
||
dp[4] = Math.max(dp[4], dp[3] + prices[i]);
|
||
}
|
||
return dp[4];
|
||
};
|
||
```
|
||
|
||
### TypeScript：
|
||
|
||
> 版本一
|
||
|
||
```typescript
|
||
function maxProfit(prices: number[]): number {
|
||
/**
|
||
dp[i][0]: 无操作;
|
||
dp[i][1]: 第一次买入；
|
||
dp[i][2]: 第一次卖出；
|
||
dp[i][3]: 第二次买入；
|
||
dp[i][4]: 第二次卖出；
|
||
*/
|
||
const length: number = prices.length;
|
||
if (length === 0) return 0;
|
||
const dp: number[][] = new Array(length).fill(0)
|
||
.map(_ => new Array(5).fill(0));
|
||
dp[0][1] = -prices[0];
|
||
dp[0][3] = -prices[0];
|
||
for (let i = 1; i < length; i++) {
|
||
dp[i][0] = dp[i - 1][0];
|
||
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
|
||
dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
|
||
dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
|
||
dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
|
||
}
|
||
return Math.max(dp[length - 1][2], dp[length - 1][4]);
|
||
};
|
||
```
|
||
|
||
### C:
|
||
|
||
```c
|
||
#define max(a, b) ((a) > (b) ? (a) : (b))
|
||
#define min(a, b) ((a) > (b) ? (b) : (a))
|
||
|
||
int maxProfit(int* prices, int pricesSize) {
|
||
int buy1 = prices[0], buy2 = prices[0];
|
||
int profit1 = 0, profit2 = 0;
|
||
for (int i = 0; i < pricesSize; ++i) {
|
||
// 寻找最低点买入
|
||
buy1 = min(buy1, prices[i]);
|
||
// 找到第一次交易的最大盈利,并不断维护这一最大值
|
||
profit1 = max(profit1, prices[i] - buy1);
|
||
|
||
// 寻找第二次交易的最低投资点，并且考虑前一次交易的成本
|
||
// 当前价格 - 第一次操作的盈利=新的投入成本（
|
||
// 为了让盈利最大，要寻找最小的成本）
|
||
buy2 = min(buy2, prices[i] - profit1);
|
||
// 第二次卖出后的盈利：当前价格减去成本，不断维护这一最大的总利润
|
||
profit2 = max(profit2, prices[i] - buy2);
|
||
}
|
||
return profit2;
|
||
}
|
||
```
|
||
|
||
|
||
|
||
### Rust：
|
||
|
||
> 版本一
|
||
|
||
```rust
|
||
impl Solution {
|
||
pub fn max_profit(prices: Vec<i32>) -> i32 {
|
||
/*
|
||
* 定义 5 种状态:
|
||
* 0: 没有操作, 1: 第一次买入, 2: 第一次卖出, 3: 第二次买入, 4: 第二次卖出
|
||
*/
|
||
let mut dp = vec![vec![0; 5]; prices.len()];
|
||
dp[0][1] = -prices[0];
|
||
dp[0][3] = -prices[0];
|
||
|
||
for (i, &p) in prices.iter().enumerate().skip(1) {
|
||
// 不操作
|
||
// dp[i][0] = dp[i - 1][0];
|
||
dp[i][1] = dp[i - 1][1].max(-p);
|
||
dp[i][2] = dp[i - 1][2].max(dp[i - 1][1] + p);
|
||
dp[i][3] = dp[i - 1][3].max(dp[i - 1][2] - p);
|
||
dp[i][4] = dp[i - 1][4].max(dp[i - 1][3] + p);
|
||
}
|
||
|
||
dp[prices.len() - 1][4]
|
||
}
|
||
}
|
||
```
|
||
|
||
> 版本二（绕）
|
||
|
||
```rust
|
||
impl Solution {
|
||
pub fn max_profit(prices: Vec<i32>) -> i32 {
|
||
let (mut one_buy, mut one_sale, mut two_buy, mut two_sale) = (-prices[0], 0, -prices[0], 0);
|
||
|
||
for p in prices {
|
||
one_buy = one_buy.max(-p);
|
||
one_sale = one_sale.max(p + one_buy);
|
||
two_buy = two_buy.max(one_sale - p);
|
||
two_sale = two_sale.max(two_buy + p);
|
||
}
|
||
two_sale
|
||
}
|
||
}
|
||
```
|
||
|
||
|