花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花排列得比较别致。
具体而言，栋栋的花的高度可以看成一列整数 。设当一部分花被移走后，剩下的花的高度依次为 ，则栋栋希望下面两个条件中至少有一个满足：
条件 A：对于所有的 ， 且 ； 条件 B：对于所有的 ， 且 。
注意上面两个条件在 时同时满足，当 时最多有一个能满足。 请问，栋栋最多能将多少株花留在原地。
链接
题解
最长波动子序列，贪心。
记录在当前情况下最长波动子序列的最后两个数，设它们为 和 ，考虑原序列最后加入一个 的影响。
如果 且 （ 且 ），则 可以接在当前最长波动子序列的后面，答案 。
如果 且 （ 且 ），则可以用 替换 ，这样一定不会使总的答案变差，并且可以使 之后一个（可能的）满足 的 接在 之后。
代码
#include <cstdio>
#include <algorithm>
const int MAXN = 100000;
int main() {
int n;
scanf("%d", &n);
int prev, curr, ans = 1;
scanf("%d", &curr);
for (int i = 1; i < n; i++) {
int x;
scanf("%d", &x);
if (x == curr) continue;
if (ans == 1 || (prev < curr) != (curr < x)) {
ans++;
prev = curr;
curr = x;
} else {
if (prev < curr) curr = std::max(curr, x);
else curr = std::min(curr, x);
}
}
printf("%d\n", ans);
return 0;
}