300. 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?

L[i]是LIS engding with nums[i]的長度，DP state transition: L[i] = max(L[j], 0 <= j <= i - 1) + 1

// Dynamic programming
int lengthOfLIS(vector<int>& nums) { // time: O(n^2); space: O(n)
    if (nums.empty()) return 0;
    int n = nums.size();
    vector<int> L(n, 1); // L[i]: the length of LIS ending with nums[i]
    int res = 1;
    for (int i = 1; i < n; ++i) {
        int mx = 0;
        for (int j = i - 1; j >= 0; --j) {
            if (nums[i] > nums[j]) mx = max(mx, L[j]);
        }
        L[i] = 1 + mx;
        res = max(res, L[i]);
    }
    return res;
}

看到time complexity是O(nlogn)就想到binary search，維護一個1D array，利用binary search找到數列裡不比當前數字小的數，如果沒有數列裡沒這個數，就直接把當前的數字加到數列裡，如果有的話，就更新該數列裡的數為當前的數字。最後數列裡的數字並不是對應到LIS的組合，只有長度剛好是LIS而已。

// Binary search with STL lower_bound
int lengthOfLIS(vector<int>& nums) { // time: O(nlogn); space: O(n)
    if (nums.empty()) return 0;
    int n = nums.size();
    vector<int> res;
    for (int i = 0; i < nums.size(); ++i) {
        auto it = lower_bound(res.begin(), res.end(), nums[i]); // lower_bound to find the first not less than nums[i]
        if (it == res.end()) res.push_back(nums[i]);
        else *it = nums[i];
    }
    return res.size();
}

// Binary search
int lengthOfLIS(vector<int>& nums) { // time: O(nlogn); space: O(n)
    if (nums.empty()) return 0;
    int n = nums.size();
    vector<int> res;
    for (int i = 0; i < nums.size(); ++i) {
        int l = 0, r = res.size();
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (res[mid] < nums[i]) l = mid + 1;
            else r = mid;
        }
        if (l == res.size()) res.push_back(nums[i]);
        else res[l] = nums[i];
    }
    return res.size();
}

674. Longest Continuous Increasing Subsequence