原题
一共两种情况，分别画图模拟一下就可以很快想出思路，线性dp分情况讨论 ，波峰与波谷交替出现，比如现在正在求f[i],那么寻找i之前比他矮（那么他就是波峰）或比他高（他是波谷），取最大值存入，并且记录他是波谷还是波峰。
代码不难实现，看懂思路就好。
#include<iostream> #include<iomanip> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,a[100007],f[100007],maxx=0,q[2][100007],head[2],tail[2]; int main() { cin>>n; if(n==1) { cout<<"1"; return 0; } for(int i=1;i<=n;++i) scanf("%d",&a[i]); for(int i=1;i<=n;++i) f[i]=1;head[0]=1;head[1]=1;tail[0]=0;tail[1]=0; for(int i=1;i<=n;++i) { int k0=0,k1=0; for(int j=head[0];j<=tail[0];++j) if(a[i]<a[q[0][j]]&&f[q[0][j]]>k0) k0=f[q[0][j]]; for(int j=head[1];j<=tail[1];++j) if(a[i]>a[q[1][j]]&&f[q[1][j]]>k1) k1=f[q[1][j]]; f[i]=max(k0,k1)+1; if(f[i]%2==0) { while(f[q[0][tail[0]]]<=f[i]&&a[i]>=a[q[0][tail[0]]]&&head[0]<=tail[0]) tail[0]--; q[0][++tail[0]]=i; } else { while(f[q[1][tail[1]]]<=f[i]&&a[i]<=a[q[1][tail[1]]]&&head[1]<=tail[1]) tail[1]--; q[1][++tail[1]]=i; } } for(int i=1;i<=n;++i) maxx=max(f[i],maxx); for(int i=1;i<=n;++i) f[i]=1;head[0]=1;head[1]=1;tail[0]=0;tail[1]=0; for(int i=1;i<=n;++i) { int k0=0,k1=0; for(int j=head[0];j<=tail[0];++j) if(a[i]>a[q[0][j]]&&f[q[0][j]]>k0) k0=f[q[0][j]]; for(int j=head[1];j<=tail[1];++j) if(a[i]<a[q[1][j]]&&f[q[1][j]]>k1) k1=f[q[1][j]]; f[i]=max(k0,k1)+1; if(f[i]%2==0) { while(f[q[0][tail[0]]]<=f[i]&&a[i]<=a[q[0][tail[0]]]&&head[0]<=tail[0]) tail[0]--; q[0][++tail[0]]=i; } else { while(f[q[1][tail[1]]]<=f[i]&&a[i]>=a[q[1][tail[1]]]&&head[1]<=tail[1]) tail[1]--; q[1][++tail[1]]=i; } } for(int i=1;i<=n;++i) maxx=max(f[i],maxx); cout<<maxx; return 0; }
