最长上升子序列(百练2757)

Posted on |

最长上升子序列(百练2757)

问题描述

一个数的序列ai，当a 1 < a 2 < … < a S 的时候，我们称这个
序列是上升的。对于给定的一个序列(a 1 , a 2 , …, a N )，我们可
以得到一些上升的子序列(a i1 , a i2 , …, a iK )，这里1 <= i1 <
i2 < … < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，
有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序
列中最长的长度是4，比如子序列(1, 3, 5, 8).
你的任务，就是对于给定的序列，求出最长上升子序列的长度

输入数据

输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出
序列中的N个整数，这些整数的取值范围都在0到10000。

输出要求

最长上升子序列的长度。

输入样例

7

1 7 3 5 9 4 8

输出样例

4

思路

求序列的前n个元素的最长上升子序列的长度”是个
子问题，但这样分解子问题，不具有“无后效性”

子问题：求以a k （k=1, 2, 3…N）为终点的最长上升子序列的
长度”

一个上升子序列中最右边的那个数，称为该子序列的
“终点”。
虽然这个子问题和原问题形式上并不完全一样，但
是只要这N个子问题都解决了，那么这N个子问题的解中，
最大的那个就是整个问题的解。

image

人人为我型递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
#include<algorithm>
#define MAX 100
int a[MAX];
int maxLen[MAX];
using namespace std;
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
	cin>>a[i];		
	maxLen[i]=1;		
	}

	for(int i=1;i<n;i++){
		for(int j=0;j<i;j++){
			if(a[i]>a[j])
			maxLen[i]=max(maxLen[j]+1,maxLen[i]);
			
		}
	}
//	int max=0;
//	for(int i=0;i<n;i++)
//	if(maxLen[i]>max) max=maxLen[i];
//	cout<<max<<endl;
	cout<<*max_element(maxLen,maxLen+n)<<endl;
	
}

我为人人型递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
#include<algorithm>
#define MAX 100
int a[MAX];
int maxLen[MAX];
using namespace std;
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
	cin>>a[i];		
	maxLen[i]=1;		
	}

	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(a[j]>a[i])
			maxLen[j]=max(maxLen[i]+1,maxLen[j]);
			
		}
	}
//	int max=0;
//	for(int i=0;i<n;i++)
//	if(maxLen[i]>max) max=maxLen[i];
//	cout<<max<<endl;
	cout<<*max_element(maxLen,maxLen+n)<<endl;
	
}

image