题目链接：
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1475
题意：Wavio sequence是指一个长度为奇数的串，以正中间的点为最高点往两端单调下降的序列，给出长为n的串，求它的最长Wavio sequence子串。
解析：对于每个点i求出从左段到i的最长单调上升子序列长度lr[i]，再求出从i到右段的最长单调下降子序列长度rl[i]，对于每个点的ans[i]为min(lr[i],rl[i])的2倍，即以i为最高点的Wavio sequence子序列。这里要用时间复杂度为O（nlogn）的算法来求最长单调上升子序列。
代码：
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M = 10005;
int ans,n,cnt;
int s[M],dp[M];
int lr[M],rl[M];
int main()
{while(scanf("%d",&n)!=EOF){memset(dp,0,sizeof(dp));ans=1;cnt=0;for(int i=1;i<=n;i++){scanf("%d",&s[i]);int k=lower_bound(dp,dp+cnt,s[i])-dp;dp[k]=s[i];if(k==cnt) cnt++;lr[i]=cnt;//lr[i]是数组a中，从左到右最长上升子序列的长度}cnt=0;memset(dp,0,sizeof(dp));for(int i=n;i>=1;i--){int k=lower_bound(dp,dp+cnt,s[i])-dp;dp[k]=s[i];if(k==cnt) cnt++;rl[i]=cnt;//rl[i]是数组a中，从右到左最长上升子序列的长度ans=max(ans,(min(rl[i],lr[i])*2));}printf("%d\n",ans-1);}return 0;
}