300. Longest Increasing Subsequence (Medium)

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,

Given [10, 9, 2, 5, 3, 7, 101, 18], The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in $$O(n^2)$$ complexity.

Follow up: Could you improve it to $$O(n log n)$$ time complexity?

Solution 1: DP (not recommended)

Time Complexity: $$O(n^2)$$ 106 ms

这道题让我们求最长递增子串Longest Increasing Subsequence的长度，简称LIS的长度。我最早接触到这道题是在LintCode上，可参见我之前的博客Longest Increasing Subsequence 最长递增子序列，那道题写的解法略微复杂，下面我们来看其他的一些解法。首先来看一种动态规划Dynamic Programming的解法，这种解法的时间复杂度为O(n2)，类似brute force的解法，我们维护一个一维dp数组，其中dp[i]表示以nums[i]为结尾的最长递增子串的长度，对于每一个nums[i]，我们从第一个数再搜索到i，如果发现某个数小于nums[i]，我们更新dp[i]，更新方法为dp[i] = max(dp[i], dp[j] + 1)，即比较当前dp[i]的值和那个小于num[i]的数的dp值加1的大小，我们就这样不断的更新dp数组，到最后dp数组中最大的值就是我们要返回的LIS的长度，参见代码如下：

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

Solution 2: DP + Binary Search

Time Complexity: $$O(n)$$ 3ms

下面我们来看一种优化时间复杂度到$$O(nlgn)$$的解法，这里用到了二分查找法，所以才能加快运行时间哇。思路是，我们先建立一个数组ends，把首元素放进去，然后比较之后的元素，如果遍历到的新元素比ends数组中的首元素小的话，替换首元素为此新元素，如果遍历到的新元素比ends数组中的末尾元素还大的话，将此新元素添加到ends数组末尾(注意不覆盖原末尾元素)。如果遍历到的新元素比ends数组首元素大，比尾元素小时，此时用二分查找法找到第一个不小于此新元素的位置，覆盖掉位置的原来的数字，以此类推直至遍历完整个nums数组，此时ends数组的长度就是我们要求的LIS的长度，特别注意的是ends数组的值可能不是一个真实的LIS，比如若输入数组nums为{4, 2， 4， 5， 3， 7}，那么算完后的ends数组为{2， 3， 5， 7}，可以发现它不是一个原数组的LIS，只是长度相等而已，千万要注意这点。参见代码如下：

version 1: binary search

int lengthOfLIS(vector<int>& nums) {
    if (nums.size() == 0) return 0;
    vector<int> ends{nums[0]};
    for (auto a: nums) {
        if (a < ends[0]) ends[0] = a;
        else if (a > ends.back()) ends.push_back(a);
        else {
            int left = 0, right = ends.size()-1;
            while (left < right) {
                int mid = (left+right)/2;
                if (ends[mid] < a) left = mid+1;
                else right = mid;
            }
            ends[left] = a;
        }
    }
    return ends.size();
}

version 2: use lower_bound

int lengthOfLIS(vector<int>& nums) {
    if (nums.size() == 0) return 0;
    vector<int> ends{nums[0]};
    for (auto a: nums) {
        if (a < ends[0]) ends[0] = a;
        else if (a > ends.back()) ends.push_back(a);
        else {
            int i = lower_bound(ends.begin(), ends.end(), a)-ends.begin();
            ends[i] = a;
        }
    }
    return ends.size();
}

Solution 3: improved DP + Binary Search

Time Complexity: $$O(n)$$ 3ms

我们来看一种思路更清晰的二分查找法，跟上面那种方法很类似，思路是先建立一个空的dp数组，然后开始遍历原数组，对于每一个遍历到的数字，我们用二分查找法在dp数组找第一个不小于它的数字，如果这个数字不存在，那么直接在dp数组后面加上遍历到的数字，如果存在，则将这个数字更新为当前遍历到的数字，最后返回dp数字的长度即可，注意的是，跟上面的方法一样，特别注意的是dp数组的值可能不是一个真实的LIS。参见代码如下：

version 1: without STL

int lengthOfLIS(vector<int>& nums) {
    vector<int> ends;
    for (auto a: nums) {
        int left = 0, right = ends.size();
        while (left < right) {
            int mid = (left+right)/2;
            if (ends[mid] < a) left = mid+1;
            else right = mid;
        }
        if (right >= ends.size()) ends.push_back(a);
        else ends[left] = a;
    }
    return ends.size();
}

version 2: with lower_bound

下面我们来看两种比较tricky的解法，利用到了C++中STL的lower_bound函数，lower_bound返回数组中第一个不小于指定值的元素，跟上面的算法类似，我们还需要一个一维数组v，然后对于遍历到的nums中每一个元素，找其lower_bound，如果没有lower_bound，说明新元素比一维数组的尾元素还要大，直接添加到数组v中，跟解法二的思路相同了。如果有lower_bound，说明新元素不是最大的，将其lower_bound替换为新元素，这个过程跟算法二的二分查找法的部分实现相同功能，最后也是返回数组v的长度，注意数组v也不一定是真实的LIS，参见代码如下：

int lengthOfLIS(vector<int>& nums) {
    vector<int> ends;
    for (auto a: nums) {
        auto it = lower_bound(ends.begin(), ends.end(), a);
        if (it == ends.end()) ends.push_back(a);
        else *it = a;
    }
    return ends.size();
}

version 3: with upper_bound

既然能用lower_bound，那么upper_bound就耐不住寂寞了，也要出来解个题。upper_bound是返回数组中第一个大于指定值的元素，和lower_bound的区别时，它不能返回和指定值相等的元素，那么当新进来的数和数组中尾元素一样大时，upper_bound无法返回这个元素，那么按算法三的处理方法是加到数组中，这样就不是严格的递增子串了，所以我们要做个处理，在处理每个新进来的元素时，先判断数组v中有无此元素，有的话直接跳过，这样就避免了相同数字的情况，参见代码如下：

int lengthOfLIS(vector<int>& nums) {
    vector<int> v;
    for (auto a : nums) {
        if (find(v.begin(), v.end(), a) != v.end()) continue;
        auto it = upper_bound(v.begin(), v.end(), a);
        if (it == v.end()) v.push_back(a);
        else *it = a;
    }
    return v.size();
}