[LeetCode] Longest Increasing Subsequence-阿里云开发者社区

[LeetCode] Longest Increasing Subsequence

2015-11-03 848

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： A typical O(n^2) solution uses dynamic programming. Let's use lens[j] to denote the length of the LIS ending with nums[j].

A typical O(n^2) solution uses dynamic programming. Let's use lens[j] to denote the length of the LIS ending with nums[j]. The state equations are

lens[0] = 1

lens[j] = max_{i = 0, 1, 2, ..., j - 1}(lens[j], lens[i] + 1)

Then the length of the LIS of nums is just the maximum value in lens. The code is as follows.

 1 class Solution {
 2 public:
 3     int lengthOfLIS(vector<int>& nums) {
 4         if (nums.empty()) return 0;
 5         int n = nums.size(), ml = 1;
 6         vector<int> lens(n, 1);
 7         for (int j = 1; j < n; j++) {
 8             for (int i = 0; i < j; i++)
 9                 if (nums[j] > nums[i])
10                     lens[j] = max(lens[j], lens[i] + 1);
11             ml = max(ml, lens[j]);
12         }
13         return ml;
14     }
15 };

The O(nlogn) solution is much more complicated. Try to read through the explanation of it in GeeksforGeeks first. The code is as follows.

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty()) return 0;
        vector<int> ends{nums[0]};
        for (int num : nums) {
            if (num < ends[0]) ends[0] = num;
            else if (num > ends.back()) ends.push_back(num);
            else {
                int l = 0, r = ends.size() - 1;
                while (l < r) {
                    int m = l + (r - l) / 2;
                    if (ends[m] < num) l = m + 1;
                    else r = m;
                }
                ends[r] = num;
            }
        }
        return ends.size();
    }
};

If you look at the else part carefully, you may notice that it can be done using lower_bound. So we will have a much shorter code, like this one.

 1 class Solution {
 2 public:
 3     int lengthOfLIS(vector<int>& nums) {
 4         vector<int> ends;
 5         for (int num : nums) {
 6             auto it = lower_bound(ends.begin(), ends.end(), num);
 7             if (it == ends.end()) ends.push_back(num);
 8             else *it = num;
 9         }
10         return ends.size();
11     }
12 };