思路与算法

维护以升或降趋势结尾的最长摆动长度；当前与上一高度比较，升则up=down+1，降则down=up+1，相等不变。

正确性说明

同向连续上升时保留更高末端不减少已有长度且更利于下一次下降，连续下降同理保留更低末端；相等无益。每次真正转向可增加一个交替段，两个趋势状态的局部替换归纳得到最长摆动子序列。

复杂度

O(n)时间、O(1)额外空间，流式读入，常数状态初始化。

易错点

严格不等，等高不增加；不是最长单调上升子序列，只有一株时答案1。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    long long last;
    cin >> last;
    int up = 1, down = 1;
    while (--n) {
        long long x;
        cin >> x;
        if (x > last)
            up = down + 1;
        else if (x < last)
            down = up + 1;
        last = x;
    }
    cout << max(up, down) << "\n";
}