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;
    }
};

Link

leetCode-122 Best Time to Buy and Sell Stock II