300 Longest Increasing Subsequence

最长递增子序列
举个例子来说明算法：

[5,6,7,1,2,8]

用一个IS矩阵来递增子序列，IS[i]表示长度为i的递增子序列。我们来看在扫描整个数组的过程中这个矩阵如何变化。

at 5:
[[], [5]]

at 6:
[[], [5],  [5,6]]

at 7:
[[], [5],  [5,6], [5,6,7]]

at 1:
[[], [1],  [5,6], [5,6,7]]

at 2:
[[], [1],  [1,2], [5,6,7]]

at 8:
[[], [1],  [1,2], [5,6,7], [5,6,7,8]]

来一个新的数，我们就往前扫描找到它可以append的位置。例如扫描到2的时候，它可以append在[1]之后形成[1,2]， 并且我们希望用[1,2]代替[5,6] 成为新的长度为2的sub sequence。

• 注意：在往前扫描的时候，每个sub sequence的最后一个数是单调的，所以可以采用binary search的方法来找到这个新的数可以插入的位置。
• 并且：每个新的数一定只有一个插入的位置。（想想为啥。）
• 这样算法的复杂度就是$$NlogN$$。

Solution-1 利用排序+最长公共子序列的方法

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if ( n == 0 or n == 1) return n;
        vector<int> help(n, 0);
        for ( int i = 0; i <= n-1; i++) help[i] = nums[i];
        sort(help.begin(), help.begin()+n);
        vector<int> result(n, 0), tmp(n, 0);
        // 1st index help's; 2nd index nums;
        result[0] = (nums[0] == help[0]);
        for ( int i = 1; i <= n-1; i++ ) {
            if ( nums[i] == help[0] ) result[i] = 1;
            else result[i] = result[i-1];
        }
        for ( int i = 1; i <= n-1; i++ ) {
            result.swap(tmp);
            if ( help[i] == help[i-1] ) {
                result = tmp;
                continue;
            }
            if ( help[i] == nums[0] ) result[0] = 1;
            else result[0] = tmp[0];
            for ( int j = 1; j <= n-1; j++ ) {
                result[j] = max(tmp[j], result[j-1]);
                if ( help[i] == nums[j] ) result[j] = max(result[j], tmp[j-1] + 1);
            }
        }
        return result[n-1];
    }
};

Solution-2
use upper_bound()

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if ( n == 0 ) return 0;
        vector<vector<int>> res(1, vector<int>(1, nums[0]));
        vector<int> help(1, nums[0]);
        for ( int i = 1; i <= n-1; i++ ) {
            int nres = res.size();
            int pos = upper_bound(help.begin(), help.end(), nums[i]) - help.begin();
            if ( pos == 0 ) {
                res[0][0] = nums[i];
                help[0] = nums[i];
                continue;
            }
            if ( res[pos-1][pos-1] == nums[i] ) continue;
            if ( pos == nres ) {
                vector<int> tmp = res[nres-1];
                tmp.push_back(nums[i]);
                res.push_back(tmp);
                help.push_back(nums[i]);
                continue;
            }
            vector<int> tmp = res[pos-1];
            tmp.push_back(nums[i]);
            res[pos] = tmp;
            help[pos] = nums[i];
        }
        return res.size();
    }
};

a simplified solution

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if ( n <= 1 ) return n;
        vector<int> res(1, nums[0]);
        for ( int i = 1; i <= n-1; i++ ) {
            int nres = res.size();
            if ( nums[i] > res[nres-1] ) {res.push_back(nums[i]); continue;}
            // firnd the first element in res ( res[j] ) s.t. res[j] > nums[i]
            for ( int j = 0; j <= nres-1; j++) {
                if ( j == 0 and nums[i] < res[j] ) {
                    res[j] = nums[i];
                    break;
                }
                if ( nums[i] < res[j] and nums[i] != res[j-1] ) {
                    res[j] = nums[i];
                    break;
                }
            }
        }
        return int(res.size());
    }
};

Converted to binary-search solution

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if ( n <= 1 ) return n;
        vector<int> res(1, nums[0]);
        for ( int i = 1; i <= n-1; i++ ) {
            int nres = res.size();
            if ( nums[i] > res[nres-1] ) {res.push_back(nums[i]); continue;}
            if ( nums[i] < res[0] ) {res[0] = nums[i]; continue;}
            if ( nums[i] == res[0] or nums[i] == res[nres-1] ) continue;
            int l = 0, r = nres-1, m; 
            // firnd the first element in res ( res[j] ) s.t. res[j] > nums[i]
            while ( true ) {
                if ( l+1 == r ) { res[r] = nums[i]; break;}
                m = (l+r)/2;
                if ( nums[i] == res[m] ) break;
                if ( nums[i] < res[m] ) r = m;
                else l = m;
            }
        }
        return int(res.size());
    }
};