分析与解法

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

比如原数组为

• A{5， 6， 7， 1， 2， 8}，

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

解法二：动态规划

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

• 要么是只包含ai的子序列
• 要么是在满足j<i并且aj<ai的以ai为结尾的递增子序列末尾，追加上ai后得到的子序列

如此，便可建立递推关系，在O(N^2)时间内解决这个问题。参考代码如下：