Description
炒股，每天股票有不同价格\(p_i\)，你每天可以买卖股票，求最大利润
Constraints
要求时间复杂度不超过\(O(nlogn)\)，\(n\)为交易日期长度
Solution
我不想说得太失礼，但这道题只看样例都知道答案了啊
但是重点还是学会证明
这道题等于算若干不重叠区间的两端差值，设第\(i\)个区间范围是\([L_i, R_i]\)，即：\(\sum_{i=1}^{n}(p_{Li} - p_{Ri})\)
这里每个区间\(i\)的起点\(L_i\)、长度\(R_i - L_i + 1\)以及区间个数\(n\)均没有限制，目标是\(\sum\)得到最大值
而不同区间获利\(p_{Li} - p_{Ri}\)可以拆分成：
\[p_{Li} - p_{Ri} = (p_{Li}-p_{Li-1}) + (p_{Li-1}-p_{Li-2}) + ... + (p_{Ri+1}-p_{Ri})\]其实只要每个分拆的小区间贡献大于0，那就是有利可图
而因为这里并没有限制获取的区间个数\(n\)，那么只要相邻的区间贡献大于0，都取了就是最优解
Code
class Solution {
public:
int maxProfit(vector<int>& prices) {
int ans = 0;
for(size_t i = 1; i < prices.size(); ++i) {
ans += max(0, prices[i] - prices[i-1]);
}
return ans;
}
};