最长连续递增子序列问题

最长递增子序列问题：

给定一个长度为N的数组，给定一个长度为N的数组，找出一个最长的单调自增子序列（不一定连续，但是顺序不能乱）。例如：给定一个长度为6的数组A{5， 6， 7， 1， 2，8}，则其最长的单调递增子序列为{5，6，7，8}，长度为4。

1

动态规划做法(时间复杂度O(N^2))

假设我们定义一个大小为n的数组a，每个元素的值分别为a0,a1,....,an-1。

我们将dpi表示为以下标为i结尾的最长递增子序列长度，那么dpi的值就等于从数组开始位置到i-1位置处找到的最大的dpj（0<j<i且ai≥aj），然后dpi = dpj + 1。

算法流程：

从数组头到尾遍历每个位置i，根据i往前找所有满足ai≥aj要求的j，且找到对应的dpj最大的哪一个j位置。遍历完整个数组之后，得到整个dp数组中最大的那个dpj便是最长递增子序列的长度。

例子：

时间复杂度：

由于要遍历一遍数组，而且遍历到每个位置i时还要往前找到最大的dpj（0<j<i且ai≥aj），因此时间复杂度为O(N^2)。

核心代码：

2

利用二分法(时间复杂度为O(NlogN))

动态规划的方法时间复杂度稍高，我们也可以利用二分法得出最长递增子序列的长度。

算法流程：

定义数组a = {5，6，7，1，2，8}

定义一个变长的临时数组tempArr，要求该数组的元素从小到大排序。

1）遍历到5，数组tempArr为空，直接加入tempArr中。

2）遍历到6，由于6大于数组中最后一个元素5，6直接加到数组后面。

3）遍历到7，由于7大于数组中最后一个元素6，7直接加到数组后面。

4）遍历到1，1小于数组中最后一个元素7，此时要在tempArr数组中找到>1最左边的元素，找到为5，然后替换掉。因为既然可以以5来往后找最长连续递增子序列，那为什么不拿1来找呢？所以这就是算法的核心

5）遍历到2，同样由于2<7，所以找到>2最左边的数，为6，替换，理由同上。

6）遍历到8，由于8>7，所以直接插入。

算法结束，最长连续递增子序列就是此时tempArr数组中的长度，为4.

整个过程为下图所示

可以看出，整个算法的核心为遍历每一个数k，然后判断k和tempArr数组中最后一个数谁大，如果k大于或者等于tempArr数组中最后一个数，则直接插入tempArr中，如果k小于tempArr数组中最后一个数，则在tempArr中找到>k的最左边的那个数，然后用k替换掉。

时间复杂度

那么在元素递增数组tempArr中找>k最左边的那个数的时候，便可以使用二分法加速该过程。因此时间复杂度为O(NlogN)。

核心代码

1