buy数组是当天买入股票可以得到的最大值（花钱的最小值），sell数组是当天卖出股票可以得到的最大值，因为要间隔一天，所以在买入的时候需要和前两天卖出的去对比。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int maxProfit(vector<int>& prices) {
int size=(int)prices.size();
if(size<2) return 0;
int* buy=new int[size];
int* sell=new int[size];
buy[0]=-prices[0];
sell[0]=0;
buy[1]=max(-prices[0],-prices[1]);
sell[1]=max(buy[1]+prices[1],0);
for(int i=2;i<size;i++){
buy[i]=max(buy[i-1],sell[i-2]-prices[i]);
sell[i]=max(sell[i-1],buy[i-1]+prices[i]);
}
return sell[size-1];
}
};
|