Longest Increasing Subsequence

https://leetcode.com/problems/longest-increasing-subsequence/description/

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(n2) complexity.

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

Thoughts

O(N^2)的DP解法参见DP章节, 这里讲二分法。

虽然也要维护一个数组, 但这次的数组的意义和DP解法的意义并不一样, 不要搞混了。 我们要维护一个tails数组, tails[i]意味着长度为i的LIS的最小结尾是多少. 用一下[https://leetcode.com/problems/longest-increasing-subsequence/discuss/]的例子:

len = 1 : [4], [5], [6], [3] => tails[0] = 3 len = 2 : [4, 5], [5, 6] => tails[1] = 5 len = 3 : [4, 5, 6] => tails[2] = 6

长度为1的LIS中尾巴最小的是3, 长度为2的尾巴最小是5...这个数组的值一定是递增的, 用反证法证明, 假如tails[i] < tails[i - 1], 也就是长度为i的LIS有一末尾a比长度为i-1的LIS 的尾巴b小, 那么长度为i-1的LIS应该选择a作为最小, 与假设不符.

既然tails是递增数组, 那么我们就可以上二分法了, 遍历nums, 对nums[i]找在tails中第一个比它大的数, 如果存在就替换它, 不存在就把tails[i] = num[i]. 比如nums 之前为[4, 5, 6, 3], 现在nums[i] = 4, tails = [3, 5, 6], 那我们用二分法把5替换成4, 得到[3, 4, 6]. 意味着长度为2的LIS现在最小的尾巴是4. 这么做的正确性其实不难看出. 因为4比3大, 也就是长度为1的LIS [3]可以和4形成一个长度为2的LIS[3, 4]. 而原来长度为2的LIS[4, 5] 由于4比5小5就被替换下去了. 最后tails的实际长度能扩张到哪, 则意味着LIS最长能有多长. 由此可见, tails 本身并不一定是对于nums的LIS, 如果问题是不光要返回长度, 还要返回具体的LIS, 是 不能 直接返回tails的.

Code

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> tails;
        for (int num : nums) {
            auto pos = lower_bound(tails.begin(), tails.end(), num);
            if ((pos - tails.begin()) < tails.size()) {
                *pos = num;
            } else {
                tails.push_back(num);
            }
        }

        return tails.size();
    }
};

Analysis

时间复杂度O(NlgN). 空间O(N).