最长上升子序列
程序员文章站
2022-05-04 11:56:20
题目描述： 给定一个长度为 N 的数列，求它数值单调递增的子序列长度最大为多少。即已知有数列 A ， A=A1,A2....An ，求 A的任意子序列 B （ B=Ak1,Ak2....Akp ），使 B 满足 k1
题目描述：
给定一个长度为 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
下一篇： Python3对比合并Excel表格