algo-aha

最长摆动子序列

• https://leetcode.com/problems/wiggle-subsequence/

int wiggleMaxLength(vector<int>& nums) {
    // 贪心法，摆动发生时增长子序列
    if (nums.empty()) return 0;
    int ans = 1;
    int prevDiff = 0;
    for (int i = 1; i < nums.size(); i++) {
        int diff = nums[i] - nums[i-1];
        if ((diff > 0 && prevDiff <= 0) || (diff < 0 && prevDiff >= 0)) {
            ans++;
            prevDiff = diff;
        }
    }
    return ans;
}

用动态规划麻烦些。O(n^2)的dp类似最长递增子序列。这里讨论O(n)的dp思路。

用up[i]表示子问题nums[0..i]、且最后上升的、最长摇摆子序列长；down[i]表示...且最后下降的...长。

int wiggleMaxLength(vector<int>& nums) {
    if (nums.empty()) return 0;
    const int N = nums.size();
    vector<int> up(N, 0), down(N, 0);
    up[0] = down[0] = 1;
    for (int i = 1; i < N; i++) {
        if (nums[i] > nums[i-1]) {
            // 设down[i-1]对应子序列的最后数是last，last可以是nums[0..i-1]间的数
            //  若last <= nums[i-1]，nums[i] > nums[i-1] >= last，可扩展down[i-1]
            //  若last > nums[i-1]，可用nums[i-1]替代last，这样nums[i] > 新last，可扩展down[i-1]
            // 所以与last大小无关，都可扩展down[i-1]
            up[i] = down[i-1] + 1;
            // 对down[i]无影响
            down[i] = down[i-1];
        } else if (nums[i] < nums[i-1]) {
            // 同理
            down[i] = up[i-1] + 1;
            up[i] = up[i-1];
        } else {
            // 不能比i-1的情况做得更好
            down[i] = down[i-1];
            up[i] = up[i-1];
        }
    }
    return max(up[N-1], down[N-1]);
}

空间优化：因为第i项只依赖于第i-1项，可将两数组优化成两变量up和down。

int wiggleMaxLength(vector<int>& nums) {
    if (nums.empty()) return 0;
    int up = 1, down = 1;
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] > nums[i-1]) {
            up = down + 1;
        } else if (nums[i] < nums[i-1]) {
            down = up + 1;
        }
    }
    return max(up, down);
}

最长摆动子段

• https://leetcode.com/problems/longest-turbulent-subarray

贪心法

int maxTurbulenceSize(vector<int>& A) {
    if (A.empty()) return 0;

    int len = 1, ans = 1;
    int prevDiff = 0;
    for (int i = 1; i < A.size(); i++) {
        int diff = A[i] - A[i-1];
        if ((diff > 0 && prevDiff <= 0) || (diff < 0 && prevDiff >= 0)) {
            len++;
        } else {
            len = diff == 0 ? 1 : 2;
        }
        ans = max(ans, len);
        prevDiff = diff;
    }
    return ans;
}

动态规划

int maxTurbulenceSize(vector<int>& A) {
    if (A.empty()) return 0;
    int up = 1, down = 1, ans = 1;
    for (int i = 1; i < A.size(); i++) {
        if (A[i] > A[i-1]) {
            up = down + 1;
            down = 1;
        } else if (A[i] < A[i-1]) {
            down = up + 1;
            up = 1;
        } else {
            up = down = 1;
        }
        ans = max({ans, up, down});
    }
    return ans;
}

摆动排序见笔记