动态规划——最长递增子序列

问题描述：给定数组p，返回p的最长公共递增子序列长度，比如p={ 2,1,5,3,6,4,8,9,7 }，最长公共子序列为{1,3,4,8,9}，所以返回长度为5.

设dp[i]表示L中以ai为末元素的最长递增子序列的长度。则有如下的递推方程：

这个递推方程的意思是，在求以ai为末元素的最长递增子序列时，找到所有序号在L前面且小于ai的元素aj，即j<i且aj<ai。如果这样的元素存在，那么对所有aj,都有一个以aj为末元素的最长递增子序列的长度dp[i]，把其中最大的dp[i]选出来，那么dp[i]就等于最大的dp[i]加上1，即以ai为末元素的最长递增子序列，等于以使dp[i]最大的那个aj为末元素的递增子序列最末再加上ai；如果这样的元素不存在，那么ai自身构成一个长度为1的以ai为末元素的递增子序列。

int lis(int *p,int n)
{
	int *dp = new int[n];
	memset(dp, 0, sizeof(int) * n);
	dp[0] = 1;
	for (int i = 1; i < n; i++)
	{
		dp[i] = 1;
		for (int j = 0; j < i; j++)
		{
			if (p[j]<p[i] && dp[j]>dp[i] - 1)
				dp[i] = dp[j] + 1;
		}
	}
	int max = -1;
	for (int i = 0; i < n; i++)
		if (dp[i] > max) max = dp[i];
	return max;
}