题目描述

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

示例:

1
2
3

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

说明:

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

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

题解

动态规划

算法

假设有数组 dp[] ，其中 dp[i] 表示到第 i 个元素时最长上升子序列（简称 LIS ）的长度，此时 nums[i] 为 LIS 最后一个元素，即 nums[i] 为子序列中最大值。
为了计算 dp[i] ，需要把当前元素 nums[i] 附加在 [0, i) 区间内所有可能的上升子序列后面，并保证附加之后的新子序列仍为上升子序列，即满足条件 nums[i] > nums[j]。
计算公式如下：

$dp[i] = \max (dp[j]) + 1, \forall 0 \leq j < i \And nums[i] > nums[j]$

LIS 长度为：

$LIS _{length} = \max (dp[i]), \forall 0 \leq i < n$

复杂度分析

时间复杂度： $O(n^2)$
空间复杂度： $O(n)$

代码

// C++
int lengthOfLIS(vector<int>& nums) {
    if (nums.empty()) {
        return 0;
    }
    vector<int> dp(nums.size());
    dp[0] = 1;
    int maxLen = 1;
    for (int i = 1; i < nums.size(); ++i) {
        int maxVal = 0;
        for (int j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                maxVal = max(maxVal, dp[j]);
            }
        }
        dp[i] = maxVal + 1;
        maxLen = max(maxLen, dp[i]);
    }
    return maxLen;
}

二分查找动态规划

算法

定义数组 tails[] ，其中 tails[i] 表示以这个元素为最大值的上升子序列，则其下标 i + 1 就是子序列的长度。保持此数组为递增序列。
定义变量 len ，表示目前最长上升子序列长度。
从左到右扫描整个数组 nums[]，对新元素 nums[i] 与 tails[0...len] 的元素做比较：
1. 如果 nums[i] 比 tails[0...len] 中所有元素小，则对 nums[i] 来说，以它为最大值的上升序列长度为 1 ，则将其放入坐标 tails[0] 。
2. 如果 nums[i] 比 tails[0...len] 中所有元素大，将 nums[i] 放入 tails[len] 。表示以 nums[i] 为最大值的上升序列长度为 len+1 ，将 len 更新为 len+1 。
3. 如果 nums[i] 在 tails[0...len] 区间内，找到第一个比 nums[i] 大的坐标 idx ，将 nums[i] 放入 tails[idx] 。表示以 nums[i] 为最大值的上升序列长度仍为 idx+1。

复杂度

时间复杂度：$O(n \log{n})$ ，二分查找耗时 $\log{n}$，调用 $n$ 次。
空间复杂度：$O(n)$

代码

// C++
int lengthOfLIS(vector<int>& nums) {
    if (nums.empty()) {
        return 0;
    }
    vector<int> tails(nums.size(), 0);
    int len = 1;
    tails[0] = nums[0];
    for (int i = 1; i < nums.size(); ++i) {
        if (nums[i] < tails[0]) {
            tails[0] = nums[i];
        } else if (nums[i] > tails[len - 1]) {
            tails[len] = nums[i];
            ++len;
        } else {
            int idx = ceilIndex(tails, -1, len - 1, nums[i]);
            tails[idx] = nums[i];
        }
        printVector(tails);
    }
    return len;
}
int ceilIndex(vector<int>& tails, int l, int r, int num) {
    while (r - l > 1) {
        int m = l + (r - l)/2;
        if (tails[m] >= num) {
            r = m;
        } else {
            l = m;
        }
    }
    return r;
}

参考链接

300. Longest Increasing Subsequence, LeetCode solution.
Longest Increasing Subsequence | DP-3, GeeksforGeeks.
Longest Increasing Subsequence Size (N log N), GeeksforGeeks.

Vault 101

LeetCode 300. 最长上升子序列

题目描述

题解

动态规划

算法

复杂度分析

代码

二分查找动态规划

算法

复杂度

代码

参考链接