陈斌彬的技术博客

Stay foolish,stay hungry

LCS的应用:最长递增子序列LIS

给定一个长度为N的数组,找出一个最长的单调递增子序列。

例如:给定数组 {5, 6, 7, 1, 2, 8},则其最长的单调递增子序列为{5,6,7,8},长度为4。

分析:其实此LIS问题可以转换成最长公子序列问题,为什么呢?

使用LCS解LIS问题原数组为A {5, 6, 7, 1, 2, 8}排序后:A’{1, 2, 5, 6, 7, 8}因为,原数组A的子序列顺序保持不变,而且排序后A’本身就是递增的,这样,就保证了两序列的最长公共子序列的递增特性。如此,若想求数组A的最长递增子序列,其实就是求数组A与它的排序数组A’的最长公共子序列。此外,本题也可以直接使用动态规划来求解