- Leetcode PHP题解--D109 122. Best T
- leetcode:122. Best Time to Buy a
- [数组]122. Best Time to Buy and Se
- Leetcode122-Best Time to Buy and
- 跟我一起刷leetCode算法题9之Best Time to B
- 121. Best Time to Buy and Sell S
- 【2019-07-30】leetcode(121-130)
- 121. Best Time to Buy and Sell S
- BestTimeToBuyAndSellStock with c
- [2018-11-18] [LeetCode-Week11] 1
image.png
只需要找连续的波谷和波峰， 在波谷买入，在波峰卖出。所以只需要判断连续的波峰和波谷就行。
可以得到证明，最低的波谷和波峰的差值，没有其中的两个波峰波谷的差值和大，画图一看就知道了。
更聪明的做法，将数组看成是时间序列，将后一个与前一个做差，只需要加起来所有的正值即可。
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;
}
};
网友评论