最长上升子序列

题目描述：

给定一个长度为 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 }

 

版权声明：本文为zhoushizheng原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/zhoushizheng/p/12499789.html