Leetcode之 Longest Increasing Subsequence

题目：

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

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. 

Note:

• 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?

代码：

方法一——普通方法，时间复杂度O(n^2)：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
         int len = nums.size();
    if (len == 0)return 0;
    vector<int> record(len + 1, 0);
    int res = 0;
    record[0] = INT_MIN;
    for (int i = 1; i <= len; i++) {
        record[i] = 1;
        for (int j = 1; j < i; j++) {
            if (nums[j - 1] < nums[i - 1]) {
                record[i] = max(record[i], record[j] + 1);      
            }
        }
         res = max(res, record[i]);
    }
    return res;
  }
};

方法二——改进方法，使用了二分，时间复杂度O(nlogn)：

// NLogN solution from geek for geek
int lengthOfLIS(vector<int>& nums) {
    if (nums.empty()) { return 0; } 
    vector<int> tail;  // keep tail value of each possible len
    tail.push_back(nums[0]);
    for (auto n : nums) {
        if (n <= tail[0]) {
            tail[0] = n;
        } else if (n > tail.back()) { // large than the tail of current largest len 
            tail.push_back(n);
        } else {  // find smallest one which is >= n
            int left = 0; 
            int right = tail.size()-1;
            int res = left;
            while(left <= right) {
                int mid = left + (right-left)/2;
                if (tail[mid] >= n) {
                    res = mid;
                    right = mid-1;
                } else { // tail[mid] < n
                    left = mid+1;
                }
            }
            tail[res] = n;
        }
    }
    return tail.size();
}

想法 ：维持一个队列