[leetcode]300-最长上升子序列

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/longest-increasing-subsequence

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

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

示例：

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

说明：

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为O(n^2)。

进阶：你能将算法的时间复杂度降低到O(nlogn)吗?

二、题解

首先要搞清楚的是题意：求最长上升子序列。子序列不是子串，两者的区别是子序列可以不连续，子串必须连续。

例如：[1, 3, 5, 2, 9]，最长上升子序列是[1, 3, 5, 9]，最长上升子串是[1, 3, 5]。

2.1 暴力法

题目的一个要求是用O(n^2)的时间复杂度来完成这个问题，如果有O(n^2)的时间复杂度，可以直接使用暴力破解的办法：

// 伪代码
for (i = 0; i < size; i++) {
    for (j = i; j < size; j++) {
        // 存在一个上升序列，和加一
        if (nums[j] >= nums[i])
            val[i][j] +=1;
    }
}

算法的时间复杂度和空间复杂度都是O(n^2)。

2.2 动态规划

以dp[i]表示到第i个元素时的最大上升子序列长度，那么dp[i]就等于数组中上一个小于5的元素的最大上升子序列长度加1。

以[10,9,2,5,3,7]为例，i=5时如何求dp[i]？此时nums[i]=7，要想构造上升序列，它前面的数字都小于7才行。左边小于7的数字有三个：2、5和3。

在数字1的地方，最大上升子序列的长度是1。
在数字5的地方，最大上升子序列的长度是2；
在数字3的地方，最大上升子序列的长度是2。

因为7大于三个数字，所以到达7的时候最大子序列长度肯定要加1，这个时候只有在上面三个数字中最大的上面加才能保证数字7的子序列最大。因此可以归纳出来的状态转移方程为：

$$dp[i]=max(dp[0], dp[1],..., dp[n]), n<i, nums[n]<=nums[i].$$

使用动态规划的时间复杂度也是O(n^2)，空间复杂度O(n)。

2.3 二分法求解

二分法不容易想出来，即使是看题解也是看了几遍才明白。

考虑一个问题：假设存在数组tails，tails[i]表示最大上升子序列长度为i的子序列的末尾元素的最小值，这种情况下tails的长度就是最大子序列的长度了。存不存在这么一个数组呢，有没有办法构造出这样的一个数组？答案是肯定的。

以[10, 9, 2, 5, 7]为例解释tails数组每个元素的意义：

所有的数字都是长度为1的子序列，其中最小的数字是2，所以tails[1]=2。
长度为2的子序列有[2, 5], [2, 7]和[5, 7]，其中末尾数最小的是5，所以tails[2]=5。
长度为3的子序列只有[2, 5, 7]，末尾数只有一个就是7，所以tails[3]=7。

如果我们能构造出这个数组，那么问题就解决了。那么关键的问题是：如何知道遍历到哪个元素的时候，它的子序列长度是多少？

首先，暂且假设这个数组存在。结合tails数组的特性，可以确定的一个问题是tails[i]肯定大于tails[i-1]，tails数组一定严格递增。因为题目求的是上升子序列，而tails数组保存的是每个子序列中的最小值，所以子序列右边的元素肯定大于左边的。

一个要注意的问题是tails[i]表示的是长度为i的子序列的末尾元素的最小值，以[1, 5, 3, 4]为例，最大上升子序列长度为2的有两个：[1, 5]和[1, 3]，如果不取最小的末尾元素3，那么tails数组就是[1, 5]，当遍历到4的时候，找到第一个大于它的数是5，此时下标等于2，也就是说最大上升子序列长度就是2。而实际上应该是3（子序列[1, 3, 4]），结果不对。

结合这个结论，在判断nums[i]的时候，只要从左到右找到第一个大于它的值的时候（使用二分法查找），这个下标就是它的最大子序列长度了。

这种情况下时间复杂度为O(nlogn)，空间复杂度为O(n)。

三、代码

3.1 动态规划

int lengthOfLIS_DP(vector<int> &nums) {
    int res = 1;
    size_t i, j;
    vector<int> dp(nums.size(), 1);

    if (nums.empty())
        return 0;

    for (i = 0; i < nums.size(); i++) {
        // 遍历所有比当前数字小的元素
        for (j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                // 更新dp数组
                dp[i] = max(dp[i], dp[j] + 1);
                // 更新结果
                res = max(dp[i], res);
            }
        }
    }

    return res;
}

3.2 二分法

通过二分法找到区间内第一个大于目标的元素：

/*
 * 在区间[left, right]找到第一个大于等于目标的元素
 * @v 待查找的数组
 * @left 左边界，包含
 * @right 右边界，包含
 * @return 找到返回元素的下标，否则返回-1
 */
int find_first_ge(vector<int> &v, int left, int right, int target) {
    int mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if (v[mid] >= target) {
            if (mid == left || v[mid - 1] < target)
                return mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

求最长上升子序列：

int lengthOfLIS_BINSEARCH(vector<int> &nums) {
    vector<int> tails(nums.size(), 0);
    int i, idx, max_len;

    if (nums.empty())
        return 0;

    max_len = 0;
    for (i = 0; i < nums.size(); i++) {
        idx = find_first_ge(tails, 0, max_len - 1, nums[i]);
        if (idx < 0) {
            // 没有找到一个比当前元素小的，扩充
            tails[max_len++] = nums[i];
        } else {
            // 找到了，替换掉
            tails[idx] = nums[i];
        }
    }
    return max_len;
}

[leetcode]300-最长上升子序列