问题
给定一个整数数组,其中第 i
个元素代表了第 i
天的股票价格
设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):
你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)
卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)
示例:
输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
思路
动规五部曲,分析如下:
确定dp数组以及下标的含义
dp[i][j]
,第i
天状态为j
,所剩的最多现金为dp[i][j]
- 出现冷冻期之后,状态其实是比较复杂度,例如今天买入股票、今天卖出股票、今天是冷冻期,都是不能操作股票的。具体可以区分出如下四个状态:
- 状态一:买入股票状态(今天买入股票,或者是之前就买入了股票然后没有操作)
- 卖出股票状态,这里就有两种卖出股票状态
- 状态二:两天前就卖出了股票,度过了冷冻期,一直没操作,今天保持卖出股票状态
- 状态三:今天卖出了股票
- 状态四:今天为冷冻期状态,但冷冻期状态不可持续,只有一天!
j
的状态为:- 0:状态一
- 1:状态二
- 2:状态三
- 3:状态四
很多题解为什么讲的比较模糊,是因为把这四个状态合并成三个状态了,其实就是把状态二和状态四合并在一起了。从代码上来看确实可以合并,但从逻辑上分析合并之后就很难理解了,所以我下面的讲解是按照这四个状态来的,把每一个状态分析清楚
注意这里的每一个状态,例如状态一,是买入股票状态并不是说今天已经就买入股票,而是说保存买入股票的状态即:可能是前几天买入的,之后一直没操作,所以保持买入股票的状态
确定递推公式
达到买入股票状态(状态一)即:
dp[i][0]
,有两个具体操作:- 操作一:前一天就是持有股票状态(状态一),
dp[i][0] = dp[i - 1][0]
- 操作二:今天买入了,有两种情况
- 前一天是冷冻期(状态四)
- 前一天是保持卖出股票状态(状态二)
- 所以操作二取最大值,即:
max(dp[i - 1][3], dp[i - 1][1]) - prices[i]
- 那么
dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i];
- 操作一:前一天就是持有股票状态(状态一),
达到保持卖出股票状态(状态二)即:
dp[i][1]
,有两个具体操作:- 操作一:前一天就是状态二
- 操作二:前一天是冷冻期(状态四)
dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
达到今天就卖出股票状态(状态三),即:
dp[i][2]
,只有一个操作:- 操作一:昨天一定是买入股票状态(状态一),今天卖出
- 即:
dp[i][2] = dp[i - 1][0] + prices[i];
达到冷冻期状态(状态四),即:
dp[i][3]
,只有一个操作:- 操作一:昨天卖出了股票(状态三),
p[i][3] = dp[i - 1][2];
- 操作一:昨天卖出了股票(状态三),
综上分析,递推代码如下:
dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i];
dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
dp[i][2] = dp[i - 1][0] + prices[i];
dp[i][3] = dp[i - 1][2];
dp数组如何初始化
- 如果是持有股票状态(状态一)那么:
dp[0][0] = -prices[0]
,买入股票所省现金为负数 - 保持卖出股票状态(状态二),第
0
天没有卖出dp[0][1]
初始化为0
就行 - 今天卖出了股票(状态三),同样
dp[0][2]
初始化为0
,因为最少收益就是0
,绝不会是负数 - 同理
dp[0][3]
也初始为0
- 如果是持有股票状态(状态一)那么:
确定遍历顺序
- 从前向后遍历
最后结果去是 状态二,状态三,和状态四的最大值,状态四是冷冻期,最后一天如果是冷冻期也可能是最大值。
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
if (n == 0) return 0;
int[][] dp = new int[n][4];
dp[0][0] -= prices[0]; // 持股票
for (int i = 1; i < n; i++) {
dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][3]);
dp[i][2] = dp[i - 1][0] + prices[i];
dp[i][3] = dp[i - 1][2];
}
return Math.max(dp[n - 1][3], Math.max(dp[n - 1][1], dp[n - 1][2]));
}
}
- 时间复杂度:O(n)
- 空间复杂度:O(n)