学步园

这个问题源于线性代数中的问题。

问题描述:设一个整数序列为A,A={a0,a1,a2,......, an}。其中任意一个递增子序列为Sk,Sk={ai,....,aj,......}, 其中ai,aj为Ak序列中任意两个元素且i<j。ai<aj。A的所有递增子序列集合为S(Sk),找出最长的Sk，即得到了最长递增子序列的长度。

举个例子，7,3,6,5,7 它的最长递增子序列为3,5,7。长度为3。

LIS问题动态规划解决方法

算法:取A中的元素ai,计算以ai结尾的必须包含ai的最长子递增序列L(i)。遍历序列A，得到 L(i)的集合L。从L中找出最长的元素L(i)，即为最长的递增子序列。

解释:设最长的递增子序列为M,则M一定会包含一个A的元素。因为M是递增的，所以M中最后一个元素M(last)是M中最大的元素。M以M(last)为ai,以ai结尾的必须包含ai的最长子递增序列”所以M必在L中。

抽象理解太难，从具体例子中发现算法。以例子说话

最长递增子序列，简称LIS。  

最大递增子序列长度，简称LOLIS   

a[1]的LOLLS为2。

a[2]的LOLLS为3

现在的问题是求a[4]的LOLLS。

一种原始的求LOLLS的方法是，找出所有以a[4]结尾的递增子序列，找出其中最长的那个子序列。

S1 = 65 239

S2 = 65 158 239

S3 = 65 170 239

S4 = 65 155 239

S5 = 65 158 170 239

Si = ...........

我们可以得到a[i]的LOLLS为4。

这种算法会搞死计算机的。即使用以后用量子计算机也无济于事。

如果能利用以前的计算结果，可能会提高计算速度。我们重新描述一下寻找以a[j]结尾的最长递增子序列长度问题。

先分解这个问题为一个小问题：

设元素a[i], i<j，求子序列s(i) = {a0,a1,....,a[i],a[j]}的最长递增子序列。

算法描述:如果a[i] < a[j]，则a[j]的LOLIS为a[i]的LOLIS +1 

如果a[i] > a[j]，则遍历ai之前对应的每一个LIS，找出最长的那个LIS，a[j]

的LOLIS，则为最长的那个LIS+1

寻找以a[j]结尾的最长递增子序列长度问题的算法，实际上是重复调用上面的小问题的算法就可以了。

算法描述：寻找以a[i]结尾的LIS(i)，i={0, ........., n}。找出LIS(i)中最大的那个LIS。

为了实现方便，可以变换一下算法的顺序：如果a[i] > a[j],，则遍历ai之前对应的每一个LIS，找出最长的那个LIS，然后加1。

代码如下

int MyGetLIS(int a[], int n)
{
	int * b = new int[n];
	memset(b, 0, sizeof(int)*n);
	b[0] = 1;

	vector<int> intVec;

	for (int i=1; i<n; ++i)
	{
		int k = 0;
		intVec.clear();
		for (int j = 0; j< i; ++j)
		{
			if (a[i] > a[j] )
			{
				intVec.push_back(b[j]);
			}
		}
		
		k = *max_element(intVec.begin(), intVec.end());
		b[i] = k+1;
	}

	for (int i=0; i<n; ++i)
	{
		cout << b[i] << endl;
	}

	cout << "Length Of LIS = " << *max_element(b, b+n) << endl;
	delete [] b;
	return 0;
}

只要俏加改动，便动得到网络上随处可见的那段求LIS问题的经典代码了。

代码如下，

int GetLIS(int a[], int n)
{
	int * b = new int[n];
	memset(b, 0, sizeof(int)*n);
	for (int i=0; i<n; ++i)
	{
		int k = 0;
		for (int j=0; j<i; ++j)
		{
			if (a[i]>a[j] && k<b[j])
			{
				k = b[j];
			}
		}

		b[i] = k + 1;
	}

	
	int m = *max_element(b, b+n);
	delete [] b;
	return m;
}

完整代码如下

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool myfn(int * i, int * j) { return (*i)<(*j); }

int GetLIS(int a[], int n)
{
	int * b = new int[n];
	memset(b, 0, sizeof(int)*n);
	for (int i=0; i<n; ++i)
	{
		int k = 0;
		for (int j=0; j<i; ++j)
		{
			if (a[i]>a[j] && k<b[j])
			{
				k = b[j];
			}
		}

		//重用计算结果
		b[i] = k + 1;
	}

	
	int m = *max_element(b, b+n);
	delete [] b;
	return m;
}

int MyGetLIS(int a[], int n)
{
	int * b = new int[n];
	memset(b, 0, sizeof(int)*n);
	b[0] = 1;

	vector<int> intVec;

	for (int i=1; i<n; ++i)
	{
		int k = 0;
		intVec.clear();
		for (int j = 0; j< i; ++j)
		{
			if (a[i] > a[j] )
			{
				intVec.push_back(b[j]);
			}
		}
		
		k = *max_element(intVec.begin(), intVec.end());
		b[i] = k+1;
	}

	for (int i=0; i<n; ++i)
	{
		cout << b[i] << endl;
	}

	cout << "Length Of LIS = " << *max_element(b, b+n) << endl;
	delete [] b;
	return 0;
}

int main()
{
	int a[]={65, 158, 170, 155, 239, 300, 207, 389};//8---5
	cout << GetLIS(a, 8) << endl;
	MyGetLIS(a, 8);
	cin.get();
	return 0;
}