题意是在一串数字中找到最长波浪子序列，即前k+1个递增，后k+1个数递减
思路比较简单，从前往后求一遍lis，在从后往前求一遍，对于每个位置，取两个dp值的最小值，最后取所有位置的dp值的最大值乘2减1
#include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<iostream> #include<algorithm> #include<vector> #include<map> #include<queue> #include<stack> #include<string>#include<map> using namespace std; #define LL long long const int maxn=10005;const int INF=1000000000;int dp1[maxn],dp2[maxn],g[maxn];int ans[maxn];int a[maxn];int main(){int n;while(scanf("%d",&n)!=EOF){for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++) g[i]=INF;for(int i=1;i<=n;i++){int k=lower_bound(g+1,g+n+1,a[i])-g;dp1[i]=k;g[k]=a[i];}for(int i=1;i<=n;i++) g[i]=INF;for(int i=n;i>=1;i–){int k=lower_bound(g+1,g+n+1,a[i])-g;dp2[i]=k;g[k]=a[i];}int answer=-INF;for(int i=1;i<=n;i++){ans[i]=2*min(dp1[i],dp2[i])-1;answer=max(answer,ans[i]);}//printf("%d\n%d\n",dp1[5],dp2[5]); printf("%d\n",answer);}}
，天下没有不散的宴席，也许这人间真的只有朦朦胧胧才是真。
