【每日算法Day 70】买卖股票的最佳时机含冷冻期
Wallace Xu 2020-08-09 动态规划
# LeetCode 309. 最佳买卖股票时机含冷冻期 (opens new window)
# 题目描述
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
# 示例
输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
1
2
3
2
3
# 解题思路
使用动态规划，规定dpSell[i]表示第i天卖出后累计的最大利润，dpBuy[i]表示第i天买入后累计的最大利润。base case为前两天的情况，dpSell[0]=0，dpBuy[0]=-prices[0]，后面要卖出时从前一天进行状态转移，而要买入时只能从前两天进行状态转移。
public int maxProfit(int[] prices) {
int n = prices.length;
if(n<2) {
return 0;
}
//初始化第一天和第二天
int[] dpBuy = new int[n], dpSell = new int[n];
dpSell[0] = 0;
dpBuy[0] = -prices[0];
dpSell[1] = Math.max(dpSell[0], dpBuy[0] + prices[1]);
dpBuy[1] = Math.max(dpBuy[0], dpSell[0] - prices[1]);
for(int i=2;i<n;++i) {
//求第i天累计卖出最大利润，累计买入的最大利润
dpSell[i] = Math.max(dpSell[i-1],dpBuy[i-1]+prices[i]);
dpBuy[i]= Math.max(dpBuy[i-1],dpSell[i-2]-prices[i]);
}
return Math.max(dpSell[n-1],dpBuy[n-1]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18