小北
0%

最长上升子序列

发表于 更新于 分类于

今早起来想起了拦截导弹问题，就又想到了最长上升子序列，前段时间学习过这个算法，但可能由于太久没练了，忘记了到底是个怎么原理，今天就打算写下来，以后就可以翻出来看看。

问题描述

上升子序列是在一串序列中，要使a1 < a2 < a3 < …… < ak,但在这里，是子序列，那就意味着他们不需要相临，但需要保持与原序列中相对的顺序是相同的。而在前面，我写了一篇kmp算法，那里是字符串匹配，那就需要是连续的，匹配到的序列应当与子串的对应起来，而在这里我们就了解如何去求最长上升子序列。

三种解法(目前先更新两种：dp和二分)

  • dp

    在一个序列中，我们可以用动态规划去求，即我们要求整个序列的最长那我们就需要先去求出前面的的最长然后保证到最后的时候仍然是最长的。

eg： 序列： 1 3 2 5 3 6
我们在这里将dp[i]记作以a[i]结尾的最长上升子序列
前1个数 a[1]=1,dp[1]=1;
前2个数 a[2]=3,a[2] > a[1],dp[2]=2;
前3个数 a[3]=2,a[3] > a[1],a[3] < a[2],dp[3]=dp[1]+1=2;
前4个数 a[4]=5,a[4] > a[1],a[4] > a[2],a[4] > a[3] ,dp[4]=dp[3]+1=3;
前5个数 a[5]=3,a[5] > a[1],a[5] > a[3],dp[5]=dp[3]+1=3;
前6个数 a[6]=6,a[6] > a[1],a[6] > a[2],a[6] > a[3],a[6] > a[4],a[6] > a[5],dp[6]=dp[5]+1=4;
在这里得出，这个最长上升子序列的元素数是4，但也可以看出最长上升子序列的选择是不唯一的，但我们可以在这里得出最长上升子序列的个数。

-代码

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
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<math.h>
using namespace std;

int main()
{
	int a[6]={1,3,2,5,3,6};
	int dp[6]={1,1,1,1,1,1};
	int i,j;
	dp[0]=1;
	int cnt=1;
	for(i=1;i<6;i++)
	{
		for(j=i-1;j>=0;j--)
		{
			if(a[i]>a[j])
			dp[i]=max(dp[i],dp[j]+1);	
		}
	}
	for(i=0;i<6;i++)
	{
		if(dp[i]>cnt)
		cnt=dp[i];
	}
	printf("%d\n",cnt);
	return 0;
}

  • 二分法求最长上升子序列

    在一串序列中，我们也可以采用替换法来求最长上升子序列，eg；我们可以用一个数组来装子序列，然后在后面的时候，去替换前面第一个比他大的位置的数。
    这里处理我们需要一个最长子序列的数组_long[],用len来记录它的长度，记得初始化全部为inf(0x3f3f3f3f).
    eg:1 3 2 5 3 6
    len=0;
    首先a[1]=1,a[1] < _long[1] (inf),_long[1]=1,len++,len=1;
    a[2]=3,a[2] < _long[2] (inf),_long [2] =3,len++,len=2;
    a[3]=2,a[3] < _long[2] (3),_long[2]=2,len=2;
    a[4]=5,a[4] < _long[3] (inf),_long[3]=5,len++,len=3;
    a[5]=3,a[5] < _long[3] (5),_long[3]=3,len=3;
    a[6]=6,a[6] < _long[4] (inf),_long[4]=6,len++,len=4;

在代码处理中，寻找_long[] 中的大于等于a[i]的数可以用c++中的lower_bund();

  • 代码如下
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    #include<stdio.h>
    #include<algorithm>
    #include<iostream>
    #include<math.h>
    #include<string.h> 
    using namespace std;

    int main()
    {
    	int a[6]={1,3,2,5,3,6};
    	int _long[6];
    	int i,j;
    	memset(_long,0x3f3f3f3f,sizeof(_long));
    	int len=0;
    	for(i=0;i<6;i++)
    	{
    		j=lower_bound(_long,_long+6,a[i])-_long+1;
    		_long[lower_bound(_long,_long+6,a[i])-_long]=a[i];
    		if(len<j)
    		len=j;	
    	}
    	printf("%d\n",len);
    	return 0;
    }

树状数组求最长上升子序列(待更新)