309. Best Time to Buy and Sell Stock with Cooldown

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
class Solution144 {
/*
* 当天 要么买 要么卖 要么停滞
* 如果买 则获利为 i-2天卖了的利润 - 当天的买价
* 如果卖 则获利为i-1天买了的利润 + 当天的卖价
* 前提 必须在买了之后才能卖
* 必须在卖了之后才能买
* 所以二者交替进行操作
* 初始化的时候 也就是第一天的时候 只能进行买操作,因而先初始化buy
*/
public:
int maxProfit(vector<int>& prices) {
int len=prices.size();
if(len==0)
return 0;
vector<int> buy(len+1,0);
vector<int> sell(len+1,0);
buy[1]=-prices[0];
for (int i = 2; i <=len ; ++i) {
sell[i]=max(sell[i-1],buy[i-1]+prices[i-1]);
buy[i]=max(buy[i-1],sell[i-2]-prices[i-1]);

}

return sell[len];
}
};