只需要找连续的波谷和波峰, 在波谷买入,在波峰卖出。所以只需要判断连续的波峰和波谷就行。
可以得到证明,最低的波谷和波峰的差值,没有其中的两个波峰波谷的差值和大,画图一看就知道了。
更聪明的做法,将数组看成是时间序列,将后一个与前一个做差,只需要加起来所有的正值即可。
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.empty()) return 0;
vector<int> f(prices.size());
int diff = 0;
for(int i = 1; i < prices.size(); i++){
f[i] = prices[i] - prices[i - 1];
if(f[i] > 0) diff += f[i];
}
return diff;
}
};
网友评论