第五章 动态规划 - 5.6 最长递增子序列

最长递增子序列

题目描述

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

分析与解法

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

比如原数组为

• 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<i并且aj<ai的以ai为结尾的递增子序列末尾，追加上ai后得到的子序列

如此，便可建立递推关系，在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");
}