leetcode-300 最长上升子序列

题目

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

分析

初步分析

第一眼感觉可能使用动态规划。参照leetcode-53最大子序和的分析思路，我们如下分析：

首先以原题目作为状态

a[n]为输入数组的内容
f(n)为前N个元素中最长子序列长度，f(n+1)与f(n)的关系并不明朗

依据leetcode-53的经验转换思路，寻找别的状态，借鉴以第N个元素结尾的子序

g(n)为以第N个元素结尾的最长上升子序列长度，上述的f(n)=max(g(k)) 0<=k<=n

那么以a[n+1]结尾的最长子序列长度可如下计算：

对于那些小于a[n+1]的元素（添加一个a[n+1]后最长上升子序列长度又会+1）把他们对应的g(n)值+1，然后取其中的最大值作为g(n+1)的值

即状态转移方程为：

g(n+1)=max(1,g(k)+1) 条件为(0<=k<=n & a[n+1]>a[k])

因此在求解时，首先是一个for循环遍历N个元素，循环内部需要根据上述状态转移方程遍历之前所有的g(k)值来求解出g(n)，并使用一个变量来保存g(n)的最大值

我们可以看到上述动态规划的求解过程时间复杂度为O(N2)，其实还有一些可优化的地方，比如 a[i] < a[j]并且g(i)>=g(j)时，那么在计算a[n]时，g(n)的最大值一定不会从a[j]上找到，a[j]此时就是无用的，因此直觉上告诉我们这个方案应该不是最优解

寻找最优解

我们的优化目标就是减少一些不比较的比较。

首先来仔细分析上述状态转移方程，其目标是：找到所有小于a[n+1]的元素，得出其中的最大的g(k)，则g(n+1)=上述最大g(k)+1。

思路1：假如我们对前n个元素排序，然后通过二分查找找到所有小于a[n+1]的元素，然后遍历他们的g(n)，这个思路引入了插入排序之后还是遍历，并不能达到期望的剪裁效果，所以此路不通

思路2：我们其实并不要一个个元素排序好，我们只是想找g(k)最大的那个小于a[n+1]的元素，所以我们可以对g(k)排序，我们从大到小遍历g(k)，如果对应的a[k]小于a[n+1]则可得出g(n+1)=g(k)+1，示例如下所示：

a[n]	g(n)
5	3
7	3
2	2
1	1

当a[n+1]=6时，由于5<6则g(n+1)=3+1（5这个元素对应的g(n)为3)，后续元素就不用再比较了，变化如下：

a[n]	g(n)
6	4
5	3
7	3
2	2
1	1

我们再来分析下上述示例，5对应的g(n)是3，7对应的g(n)也是3，那么新来一个元素时，只需要跟5比即可，无需跟7比，即同一个g(n)值只需要保留1个最小值即可，即变化如下：

a[n]	g(n)
6	4
5	3
2	2
1	1

这样的话，g(n)的值便是从1开始连续递增的，并且最大值或者说保留下来的g(n)的个数就是最终我们要的结果，下次再来一个新元素的话，我们只比较m个元素即可（m=max(g(n))），大大减少了我们的比较量，可以看到这种优化其实就是利用到了上述动态规划中没有利用到的优化点

同时我们再思考下此时相邻g(n)之间他们对应的a[n]之间的关系。比如元素b对应的g(n)=2，元素c对应的g(n)=3，有没有可能c<b？假如c小于b，那么在得出c对应的g(n)=3的过程中，必然是g(n)=2的元素+1得到，则必然g(n)=2对应的元素小于c才会去执行+1操作来得到c对应的g(n)值，所以必然有c<b，即g(n)是从大到小排好序的，对应的a[n]也是从大到小排好序的，他们的个数即为我们要的最终结果

所以最终在实施的时候，对a[n]进行排序，假如新来一个元素比最大a[n]要大，则该元素直接填充，如果新来一个元素介于2个元素b、c之间，c>b，必有c对应的g(n)值=b对应的g(n)值+1，那么根据上述求g(n)的逻辑，该元素的对应的g(n)值=b对应的g(n)值+1即和c对应的g(n)值是一样的，再利用同一个g(n)值取最小的特点，那么新来的元素就要替换掉c

以上述为例，再来一个元素3时，3介于5和2之间，3对应的g(n)值=2对应的g(n)值+1，则3和5的g(n)值同为3，再利用相同g(n)值取最小的逻辑，最终演变成3替换掉第一个大于它的值即5

a[n]	g(n)
6	4
5	3
3	3
2	2
1	1

演变成

a[n]	g(n)
6	4
3	3
2	2
1	1

综上所述：新来一个元素如果大于上述a[n]中的最大值则填充，否则就要替换第一个大于该值的位置（即通过二分查找即可）

代码

动态规划的解法如下，时间复杂度O(n2)：

public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int fn = 1;
    int[] gnArr = new int[nums.length];
    gnArr[0] = 1;
    for (int i = 1; i < nums.length; i++) {
        int max = 1;
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                max = Math.max(max, gnArr[j] + 1);
            }
        }
        gnArr[i] = max;
        fn = Math.max(fn, max);
    }
    return fn;
}

第二套优化方案，时间复杂度O(nlogn)

public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int[] d = new int[nums.length];
    int pos = 0;
    d[pos] = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > d[pos]) {
            pos++;
            d[pos] = nums[i];
        } else {
            d[binarySearch(d, pos, nums[i])] = nums[i];
        }
    }
    return pos + 1;
}

private int binarySearch(int[] arr, int end, int key) {
    int left = 0;
    int right = end;
    int mid;
    while (left < right) {
        mid = left + (right - left) / 2;
        if (arr[mid] >= key) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

跑分

欢迎关注微信公众号：乒乓狂魔