题目来源
一道DP题，但是想不到怎么进行DP。
我一开始的想法是先从前往后遍历，不管条件限制把最优情况先求出来，然后再遍历，扣掉不满足条件的部分。
代码如下：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size(), res = 0;
for (int i=1; i<n; i++)
if (prices[i] > prices[i-1])
res += prices[i] - prices[i-1];
for (int i=3; i<n; i++)
if (prices[i] > prices[i-1] && prices[i-1] < prices[i-2] && prices[i-2] > prices[i-3])
res -= min(prices[i]-prices[i-1], prices[i-2]-prices[i-3]);
return res;
}
};
答案是错的，我没有考虑这种情况，[6,1,3,2,4,7]，直接买1卖7比较合算。
然后我想着要不记录下每个上升的头尾，然后进行处理。
然后我就放弃了。直接看讨论区。
然后我又被大神们折服了。
分为sell，buy，rest三种进行讨论，然后根据实际情况进行简化。
具体看讨论区。
代码如下：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int sell(0), buy(INT_MIN), prev_sell(0), prev_buy;
for (int price : prices) {
prev_buy = buy;
buy = max(prev_sell-price, buy);
prev_sell = sell;
sell = max(prev_buy+price, sell);
}
return sell;
}
};
