给定一个序列，求其中最长波动子序列

题解

据说这题可以动归，然而感觉动归爆炸，就贪了个心

正解是枚举所有的拐点，将拐点加入子序列中一定比加入其他点更优，因为拐点比可以容纳更多的点在其中波动，最后特判起点和终点是否可以加入序列中即可

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
const int MAXN = 100000;
int height[MAXN + 1];
int main () {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &height[i]);
    }
    
    bool isUping = true; int ans = 0;
    if (height[1] >= height[2]) isUping = false;
    else isUping = true;
    for (int i = 2; i <= n - 1; i++) {
        if (isUping && height[i] > height[i + 1]) {
            isUping = false;
            ans++;
        } else if (!isUping && height[i] < height[i + 1]) {
            isUping = true;
            ans++;
        }
    }
    if (height[1] == height[2]) ans--;
    if (height[n - 1] == height[n]) ans--;
    ans += 2;
    printf("%d\n", ans);
    return 0;
}