算法：最长递增子序列

一、题目描述

给定一个长度为N的数组a0,a1,a2…,an-1，找出一个最长的单调递增子序列（注：递增的意思是对于任意的i

二、分析与解法

解法一：转换为最长公共子序列问题

比如原数组为

A{5， 6， 7， 1， 2， 8}，
当我们对这个数组进行排序后，排序后的数组为：

A‘{1， 2， 5， 6， 7， 8}。
然后想求数组A的最长递增子序列，其实就是求数组A与它的排序数组A‘的最长公共子序列，原因是原数组A的子序列顺序保持不变，而且排序后A‘本身就是递增的，这样，就保证了两序列的最长公共子序列的递增特性。

如此，若想求数组A的最长递增子序列，其实就是求数组A与它的排序数组A‘的最长公共子序列。

解法二：动态规划

想到这个问题不能改变元素各自的相对顺序，所以我们不能排序，在不能排序的情况下，我们考虑下是否能用动态规划解决。

定义dp[i]为以ai为末尾的最长递增子序列的长度，故以ai结尾的递增子序列

要么是只包含ai的子序列
要么是在满足j 如此，便可建立递推关系，在O(N^2)时间内解决这个问题。参考代码如下：

int n;
int a[n];

int dp[n];

void lis()
{
	int res = 0;
	int i;
	for (i = 0; i < n; i++)
	{
		dp[i] = (dp[i] > dp[i + 1] )? dp[i]:dp[i + 1];
	}
	res = (res > dp[i])?res:dp[i];
	printf("%d\n,res");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16