最长上升子序列

0
10

题目描述:

给定一个长度为N的数列,求它数值单调递增的子序列长度最大为多少。即已知有数列A,A=A1,A2….An,求A的任意子序列B(B=Ak1,Ak2….Akp),使B满足k1<k2<….<kp且Ak1<Ak2<….<Akp。

现求p的最大值。

输入格式

共二行。

第一行是一个整数N,N个数。

第二行有n个整数

输出格式

一个整数,最长上升子序列长度

输入输出样例

输入
8
186 186 150 200 160 130 197 220
输出
4
代码

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<iostream>
 4 using namespace std;
 5 int n,a[105],dp[105],ans;
 6 int main()
 7 {
 8     cin>>n; 
 9     for(int i=0;i<n;i++) 
10     {
11         cin>>a[i];
12     }
13     for(int i=0;i<n;i++) 
14     {
15         dp[i]=1;
16         for(int j=0;j<n;j++) 
17         {
18             if(a[i]>a[j]) 
19             {
20                 dp[i]=max(dp[i],dp[j]+1);
21             }
22         }
23     }
24     int maxx=0;
25     for(int i=0;i<n;i++)
26     {
27         maxx=max(maxx,dp[i]);
28     }
29     cout<<maxx;
30     return 0;
31 }

ccc

<

发布回复

请输入评论!
请输入你的名字