309. Best Time to Buy and Sell Stock with Cooldown
程序员文章站
2022-06-17 18:52:36
...
309. Best Time to Buy and Sell Stock with Cooldown
含有冷冻期的买卖股票的最佳时期
题目:
给定一个数组,代表每天股票的价格,你可以交易任意次,但必须遵循以下规则:
①必须在下一次买之前先卖出去;
②卖出股票的第二天为冷冻期,不能接着买股票
解题思路:
buy[i]表示在第i天之前最后一个操作是买,此时的最大收益。
sell[i]表示在第i天之前最后一个操作是卖,此时的最大收益。
rest[i]表示在第i天之前最后一个操作是冷冻期,此时的最大收益。
递推式:
buy[i] = max(rest[i-1] - price, buy[i-1])
sell[i] = max(buy[i-1] + price, sell[i-1])
rest[i] = max(sell[i-1], buy[i-1], rest[i-1])
但是我们要提防[buy,rest,buy]的出现,因为buy[i]<=rest[i],所以rest[i]=max(sell[i-1], rest[i-1]),就会保证[buy,rest,buy]不出现。
另外,由于冷冻期的存在,所以rest[i]=sell[i-1]。因此,递推式便可以精简为:
buy[i] = max(rest[i-1] - price, buy[i-1])
sell[i] = max(buy[i-1] + price, sell[i-1])
代码:
class Solution {
public int maxProfit(int[] prices) {
if(prices==null || prices.length<=0) return 0;
int b0=-prices[0], b1=b0;
int s0=0, s1=0, s2=0;
for(int i=1;i<prices.length;i++)
{
b0=Math.max(s2-prices[i], b1);
s0=Math.max(s1, b1+prices[i]);
b1=b0; s2=s1; s1=s0;
}
return s0;
}
}
上一篇: JSON简介
下一篇: listview 的滑动
推荐阅读
-
LeetCode_Array_123. Best Time to Buy and Sell Stock III买卖股票的最佳时机III(C++)
-
Leetcode No.121 Best Time to Buy and Sell Stock(c++实现)
-
309. Best Time to Buy and Sell Stock with Cooldown
-
Leetcode 309. Best Time to Buy and Sell Stock with Cooldown
-
[LeetCode] 309. Best Time to Buy and Sell Stock with Cooldown
-
【DP + 卖股票】LeetCode 309. Best Time to Buy and Sell Stock with Cooldown
-
LeetCode题解系列--309. Best Time to Buy and Sell Stock with Cooldown
-
动态规划-309. Best Time to Buy and Sell Stock with Cooldown
-
(M)Dynamic Programming:309. Best Time to Buy and Sell Stock with Cooldown
-
309. Best Time to Buy and Sell Stock with Cooldown