一开始WA了 参考了一下 求正反两个方向的最长上升子序列 并分别记录在两个数组中 最后求最大值
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;int a[10010],c1[10010],c2[10010],d[10010];
int cc(int n, int& i)
{
if(i == 0 || d[i] < n)
{
d[++i] = n;
}
else
{
int p = lower_bound(d, d+i, n) - d;
d[p] = n;
}
return i;
}
int main()
{
int n;
while(scanf("%d",&n) == 1)
{
memset(c1, 0, sizeof(c1));
memset(c2, 0, sizeof(c2));
int c = 0, _max = 0;
for(int i = 0; i < n; i++)
{
scanf("%d",&a[i]);
c1[i] = cc(a[i], c);
}
c = 0;
for(int i = n-1; i >= 0; i--)
{
c2[i] = cc(a[i],c);
}
for(int i = 0; i < n; i++)
{
_max = max(_max, min(c1[i], c2[i]));
}
printf("%d\n",_max*2-1);
}
return 0;
}