文章目录

1. 1. 题目
2. 2. 分析

题目

---

给定一个长度为N的数组a0,a1,a2…,an-1，找出一个最长的单调递增子序列（注：递增的意思是对于任意的i<j，都满足ai<aj，此外子序列的意思是不要求连续，顺序不乱即可）。例如：给定一个长度为6的数组A{5，6，7，1，2，8}，则其最长的单调递增子序列为{5，6，7，8}，长度为4。

分析

---

可以采用单步判决的思想，对每一个长度的序列进行计算获取其LIS，即动态规划的思想，例如假设LIS[i]为序列a[0…..i]的最长递增子序列的长度。则对于每一个a[i]需要考虑的是
1、首先假定a[i]自己成为一个递增子序列，长度为1；
2、逐一判断其前面的每一个值a[j]与a[i]的大小,如果a[j]LIS[i]，则更新LIS[i]
复杂度为O(n^2),如果要输出最长递增子序列，可以设置一个数组记录a[0….i]的最长递增子序列中前一个位置的下标，最后反向输出即可，实现如下。完整代码下载在githib-eesly

int LIS(int a[],int n)
{
	int len = n;
	int *dp = new int[n];	//dp[i]表示a[0...i]的最长序列长度
	int *last_index = new int[n];//记录dp[i]表示的最长子序列上一个位置下标*********
	int end = 0;			//记录最终的最长子序列最后一个值的下表*********
	int rs = 0;
	for(int i = 0; i<n; i++)
	{
		//每个位置最初的递增序列长度为1，即序列只有一个值为其本身
		dp[i]=1;
		last_index[i] = i;	//*********
		//检查该值前面的每一个值，如果当前值大于它
		//则比较LIS[当前值]与LIS[前面值]+1的大小,如果其更大则更新
		//这样经过O(n^2)可以获得最长的递增序列长度
		for(int j = 0;j<i;j++)
			if(a[j]<a[i] && dp[i]<dp[j]+1)
			{
				dp[i]=dp[j]+1;
				last_index[i] = j;//*********
			}
		if(dp[i]>rs)
		{
			rs = dp[i];
			end = i;			//*********
		}
	}
	int sublen = rs;
	while(sublen--)				//*********
	{							//*********
		cout<<a[end]<<" ";		//*********
		end = last_index[end];	//*********
	}							//*********
	cout<<endl;					//*********
	return rs;
}
/------------------------------------------------------------/
给个精简版
int LIS(int a[],int n)
{
	int len = n;
	int *dp = new int[n];	//dp[i]表示a[0...i]的最长序列长度
	int rs = 0;
	for(int i = 0; i<n; i++)
	{
		//每个位置最初的递增序列长度为1，即序列只有一个值为其本身
		dp[i]=1;
		//检查该值前面的每一个值，如果当前值大于它
		//则比较LIS[当前值]与LIS[前面值]+1的大小,如果其更大则更新
		//这样经过O(n^2)可以获得最长的递增序列长度
		for(int j = 0;j<i;j++)
			if(a[j]<a[i] && dp[i]<dp[j]+1)
				dp[i]=dp[j]+1;
		if(dp[i]>rs)
			rs = dp[i];
	}
	return rs;
}