波动序列的定义不用多说，下面给出波动序列的求法。
#include<iostream>
#include<cstdio>
#define N 100002
using namespace std;
int n,a[N],dp[N][];
int main(){
scanf("%d",&n);
for(int i=;i<=n;++i)scanf("%d",&a[i]);dp[][]=dp[][]=;
for(int i=;i<=n;++i){
if(a[i]>a[i-])dp[i][]=dp[i-][]+;
else dp[i][]=dp[i-][];
if(a[i]<a[i-])dp[i][]=dp[i-][]+;
else dp[i][]=dp[i-][];
}
cout<<max(dp[n][],dp[n][]);
return ;
}
这里有一个结论，就是存在一个最优解的末尾为数列的最后一个点。
证明：
假设当前是一个下降的最优的波动序列，遇到了下一个点。
1.当前高度与上一个的高度相等，那这两个点选谁也无所谓，直接用当前点覆盖上一个点。
2.当前高度比上一个高度低，那我也可以用这个点替换上一个点，因为当前是山谷，山谷越低，对于下一个点来说成为山峰的概率越大。
3.当前高度比上一个高度高，那我可以直接把这个点纳入这个序列，序列长度+1。
三种情况讨论完毕。
上升的情况同理。
证毕。