300.longest-increasing-subsequence

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

1.普通dp O(n^2)

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n,0);
        int res = 0;
        for(int i = 0; i < n; i++) {
            int cur = 0;
            for(int j = 0; j < i; j++) {
                if(nums[j] < nums[i] && dp[j] > cur) {
                    cur = dp[j];
                }
            }
            dp[i] = cur + 1;
            if(dp[i] > res) res = dp[i];
        }
        return res;
    }
};

2.Greedy+binary search优化

Robinson-Schensted-Knuth Algorithm
分三种情况，smallest，largest，mid。

class Solution {
    int binarySearch(vector<int> &ends, int last, int x) {
        int l = 0;
        int r = last;
        while(l < r) {
            int m = l + (r - l)/2 + 1;
            if(ends[m] >= x) {
                r = m - 1;
            } else {
                l = m;
            }
        }
        return l;
    }
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) {return 0;}
        vector<int> ends(n,0);
        int last= 0;
        ends[0] = nums[0];
        for(int i = 1; i < n; i++) {
            if(nums[i] < ends[0]) { //smallest
                ends[0] = nums[i];
            } else if(nums[i] > ends[last]) {  //largest
                ends[++last] = nums[i];
            } else {  //mid
                int j = binarySearch(ends,last,nums[i]); //找到最大的小于x的值
                ends[j+1] = nums[i];
            }
        }
        return last+ 1;
    }
};

Follow Up:

1.输出sequence
以下方法输出最后一个匹配上的sequence，如果想输出最先匹配上的，可以从后往前做longest decrease sequence，再输出。

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    if(n == 0) {return 0;}
    vector<int> ends(n,0);
    vector<int> pos(n,0);
    int last= 0;
    ends[0] = nums[0];
    pos[0] = 0;
    for(int i = 1; i < n; i++) {
        if(nums[i] < ends[0]) { //smallest
            ends[0] = nums[i];
            pos[i] = 0;
        } else if(nums[i] > ends[last]) {  //largest
            ends[++last] = nums[i];
            pos[i] = last;
        } else {  //mid
            int j = binarySearch(ends,last,nums[i]); //找到最大的小于x的值
            ends[j+1] = nums[i];
            pos[i] = j+1;
        }
    }
    //倒序输出
    int k = n-1;
    int i = last;
    while(k >= 0) {
        if(i == -1) break;
        if(pos[k] == i) {
            cout<<nums[k]<<" ";
            i--;
        }
        k--;
    }
    return last+ 1;
}

2.求longest非严格递增的序列
binarySearch的时候找的时候，找<=x的值而不是<x的值即可。

3.输出所有的递增序列
感觉像是个排列组合问题。

334.increasing-triplet-subsequence

https://leetcode.com/problems/increasing-triplet-subsequence/
思路类似300，ends容量为3。

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int n = nums.size();
        if(n < 3) return false;
        vector<int> ends(3);
        int last = 0; //last = len - 1
        ends[0] = nums[0];
        for(int i = 1; i < n; i++) {
            if(nums[i] < ends[0]) {
                ends[0] = nums[i];
            } else if(nums[i] > ends[last]) {
                ends[++last] = nums[i];
                if(last== 2) return true;
            } else {
                for(int j = 0; j < 3; j++) {
                    if(ends[j] == nums[i]) {
                        break;
                    } else {
                        if(nums[i] < ends[j]) 
                            ends[j] = nums[i];
                    }
                }
            }
        }
        return false;
    }
};

354.Russian Doll Envelopes

https://leetcode.com/problems/russian-doll-envelopes/
暴力的思路就是用DP直接求解。

用binary search优化则用以下思路：
先用w排序，再对h用300做LIS即可，注意，因为要求严格递增，所以宽度需要有额外的判断。
见discuss，机智点在于排序的时候first按升序排second按降序排。所以second1>second2，意味着first1>first2。代码来自discuss，二分法部分我改成了我习惯的模式。
https://leetcode.com/discuss/106939/c-time-o-nlogn-space-o-n-similar-to-lis-nlogn-solution

bool cmp (pair<int, int> i, pair<int, int> j) {
    if (i.first == j.first)
        return i.second > j.second;
    return i.first < j.first;
}

class Solution {
public:
    int maxEnvelopes(vector<pair<int, int>>& envelopes) {
        int N = envelopes.size();
        vector<int> candidates;
        sort(envelopes.begin(), envelopes.end(), cmp);
        for (int i = 0; i < N; i++) {
            int lo = 0, hi = candidates.size();
            while (lo < hi) {
                int mid = lo + (hi - lo)/2;
                if (envelopes[i].second > envelopes[candidates[mid]].second)
                    lo = mid + 1;
                else
                    hi = mid;
            }
            if (lo == candidates.size())
                candidates.push_back(i);
            else
                candidates[lo] = i;
        }
        return candidates.size();
    }
};