LeetCode 309 Best Time to Buy and Sell Stock with Cooldown

炒股,能够买卖多次,但是每次买完需要等一天才能再次买入,问最多能赚多少钱

炒股系列第四题了,还是用动态规划来做,b代表当前已买入的情况下的最大收益,s[i]表示第i天前已卖出时的最大收益,prev_s表示上次在第i天卖出时的最大收益。

b = max(b, prev_s[i-2] - prices[i]);

s[i] = max(prev_s[i], s[i-1], b+prices[i])分别表示上一次在第i天卖出,在第i天不卖出和在第i天卖出的最大值。

C++ Code

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
28
class Solution {
public:
int maxProfit(vector<int>& prices) {
int sz = prices.size();
if(sz == 0) {
return 0;
}
vector<int> s(sz, -0x7fffffff);
vector<int> prev_s;
int b = -0x7fffffff;
for(int i = 0; i < sz; ++i) {
b = max(b, -prices[i]);
if(i > 0)
s[i] = s[i-1];
s[i] = max(s[i], prices[i] + b);
}
for(int j = 2; j < sz; j += 2) {
b = -0x7fffffff;
prev_s = s;
for(int i = j; i < sz; ++i) {
b = max(b, prev_s[i-2] - prices[i]);
s[i] = max(s[i], s[i-1]);
s[i] = max(s[i], b + prices[i]);
}
}
return s[sz-1];
}
};