首页 > 代码库 > 怪盗基德的滑翔翼(还是最长x序列)

怪盗基德的滑翔翼(还是最长x序列)

技术分享
 1 //怪盗基德的滑翔翼
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstdlib> 
 5 #include<cstring>
 6 using namespace std;
 7 const int maxx=102;
 8 int a[maxx],b[maxx],c[maxx];
 9 int main()
10 {
11     int n,t;
12     scanf("%d",&t);
13     while(t--)
14     {
15         memset(b,0,sizeof(b));
16         memset(c,0,sizeof(c));
17         scanf("%d",&n);
18        for(int i=1;i<=n;i++)
19        scanf("%d",&a[i]);
20        for(int i=1;i<=n;i++)
21        {
22            b[i]=1;
23            for(int j=1;j<=i-1;j++)
24            {
25                if(a[j]<a[i]&&b[i]<b[j]+1)
26                b[i]=b[j]+1;
27            }
28        }
29        for(int i=n;i>=1;i--)
30        {
31            c[i]=1;
32            for(int j=i+1;j<=n;j++)
33            {
34                if(a[j]<a[i]&&c[i]<c[j]+1)
35                c[i]=c[j]+1;
36            }
37        }
38        int maxl=0;
39        for(int i=1;i<=n;i++)
40        {
41            if(b[i]>maxl)maxl=b[i];
42            if(c[i]>maxl)maxl=c[i];
43        }
44        printf("%d\n",maxl);
45     }
46     return 0;
47 }
View Code

 

怪盗基德的滑翔翼(还是最长x序列)