Kotlin程序员求解最长递增子序列长度

【出自WR面试题】

难度系数：★★★★☆ 被考察系数：★★★★☆

题目描述：

假设L=＜a1，a2，…，an＞是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=＜ak1，ak2，…，akm＞，其中，k1＜k2＜…＜km且ak1＜ak2＜…＜akm。求最大的m值。

方法一：最长公共子串法

对序列L=＜a1，a2，…，an＞按递增进行排序得到序列LO=＜b1，b2，…，bn＞。显然，L与LO的最长公共子序列就是L的最长递增子序列。因此，可以使用求公共子序列的方法来求解。

方法二：动态规划法

由于以第i个元素为结尾的最长递增子序列只与以第i-1个元素为结尾的最长递增子序列有关，因此，本题可以采用动态规划的方法来解决。下面首先介绍动态规划方法中的核心内容递归表达式的求解。

以第i个元素为结尾的最长递增子序列的取值有两种可能：

（1）1，第i个元素单独作为一个子串（L[i]＜=L[i-1]）。(www.xing528.com)

（2）以第i-1个元素为结尾的最长递增子序列加1（L[i]＞L[i-1]）。

由此可以得到如下的递归表达式：假设maxLen[i]表示以第i个元素为结尾的最长递增子序列，那么

（1）maxLen[i]=max{1，maxLen[j]+1}，j＜iandL[j]＜L[i]

（2）maxLen[0]=1

根据这个递归表达式可以非常容易地写出实现的代码：

程序的运行结果如下：

xbcdza最长递增子序列的长度为：4

算法性能分析：

由于这种方法用双重循环来实现，因此，这种方法的时间复杂度为O（N^2），此外由于这种方法还使用了N个额外的存储空间，因此，空间复杂度为O（N）。