贪心算法进阶：摆动序列、递增三元组及股票买卖实战

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int a = nums[0];
        int b = INT_MAX;
        int sz = nums.size();
        for(int i = 1; i < sz; ++i) {
            if(nums[i] > b) return true;
            if(a > nums[i]) a = nums[i];
            else if(nums[i] != a) b = nums[i];
            else continue;
        }
        return false;
    }
};

3. LeetCode 674. 最长连续递增序列

要求连续的递增子数组。相比非连续子序列，这里只需要一次线性遍历。维护当前连续长度和最大长度，遇到不满足递增条件的情况则重置当前长度。

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int ret = 1;
        int ret1 = 1;
        int sz = nums.size();
        for(int i = 0; i < sz - 1; ++i) {
            if(nums[i+1] > nums[i]) ret1++;
            else ret1 = 1;
            if(ret1 > ret) ret = ret1;
        }
        return ret;
    }
};

4. LeetCode 121. 买卖股票的最佳时机

目标是找到两数之差的最大值。贪心点在于不断更新历史最低价。遍历时，用当前价格减去历史最低价得到潜在利润，同时若当前价格更低则更新最低价。

class Solution {
public:
    int maxProfit(vector<int>& p) {
        int sz = p.size();
        int ret = 0;
        int l = INT_MAX; // 买
        for(int i = 0; i < sz; ++i) {
            if(l < p[i]) ret = max(ret, p[i] - l);
            if(l > p[i]) l = p[i];
        }
        return ret;
    }
};