【动态规划】最长单调子序列

最长单调递增子序列

算法思路：

1.该问题最有最优子结构性质。当n个数最长时，n-1个数也一定是最长的。

2.定义一个数组dp[i]，记录以a[i]结尾的最长单调递增子序列长度。

3.a[0]~a[i-1]中比a[i]小的都可以作为倒数第二个数，找到其中dp[j]最大的数作为倒数第二个数。

4.找到a[0]~a[k]中把a[j]小且dp[]值最大的数作为倒数第三个数。

5.重复类似3、4步的过程，就可以找到整个以a[i]结尾的最长单调递增子序列。

6.假设dp[k]是dp[]数组中的最大值，则由n个数组成的序列的最长单调递增子序列就是以a[k]结尾的的序列，最大长度为dp[k]

由上可以推出递推式：dp[i]=d[j]+1 j<i&&dp[j]=max(dp[0]~dp[i-1])

7.怎么复现这个递增子序列呢？这里可以采用排队的思想。我们平时排队时，只要记住自己前面的人是谁，就可以复原整个有序队列。这里也一样，让每个a[i]记住自己的前一个数是a[j]。

代码实现:

#include<bits/stdc++.h>
using namespace std;
#define N 10010
int n;
int a[N],dp[N],lis[N],pre[N];
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	dp[0]=1;
	int max_len=0,max_inx=0;
	for(int i=0;i<n;i++){
		int max_dp=0;
		int inx=0;
		for(int j=0;j<i;j++){
			if(a[j]<a[i] && dp[j]>max_dp){
				max_dp=dp[j];
				inx=j;
			}
		}
		dp[i]=max_dp+1;
		pre[i]=inx;  //记录有序序列每个数的前一个数 
		if(dp[i]>max_len){
			max_len=dp[i];
			max_inx=i;
		}
	}
	for(int i=max_len-1;i>=0;i--){
		lis[i]=a[max_inx];
		max_inx=pre[max_inx];
	}
	for(int i=0;i<max_len;i++) printf("%d ",lis[i]);
	return 0;
}
 
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
29
30
31
32
33
34

测试：