300. Longest Increasing Subsequence

brute force做的话，递归来做，每个元素在不在subsequence中，时间复杂度O(2^n)

 

方法一：DP

由于只需要求个数，不需要把subsequence求出来，很自然想到dp

dp[i] 表示以 a[i] 为结尾的最长字串的长度，

dp[i] = max(dp[j]+1)  ∀0<=j<i

最后的结果就是 max(dp[i])  ∀i

时间复杂度 O(n^2)

class Solution {public:    int lengthOfLIS(vector
     
      & nums) {        vector
      
        dp(nums.size(),1);        for (int i=0;i
      
     

 

方法二：Binary Search

类似模拟的方法，二分寻找大于等于当前元素的下标。时间复杂度O(nlogn)，详见

class Solution {public:    int lengthOfLIS(vector
     
      & nums) {        vector
      
        tmp;        for (int num:nums){            if (tmp.empty()||num>tmp.back())                tmp.push_back(num);            else{                int index=lower_bound(tmp,num);                tmp[index] = num;            }        }        return tmp.size();    }        int lower_bound(vector
       
         &a, int x){        int low=0, high=a.size();        while (low
       
      
     

 

 

354. Russian Doll Envelopes

Longest Increasing Subsequence的二维进阶，其实方法是一样的。

方法一：DP

先对数组排序一下，然后就是Longest Increasing Subsequence的问题了，用dp求解。

class Solution {public:    int maxEnvelopes(vector
     
      
       >& envelopes) {        int n=envelopes.size();        sort(envelopes.begin(),envelopes.end());        vector
       
         dp(n,1);        int res=0;        for (int i=0;i
        
         envelopes[j].first && envelopes[i].second>envelopes[j].second){                    dp[i] = max(dp[i], dp[j]+1);                }            }            res = max(res, dp[i]);        }        return res;    }};
        
       
      
     

 

方法二：二分

想办法把这个问题划归到一维的问题。对envelopes排序，对宽从小到大，如果宽相同，说明这两个信封不能同时取到，把高小的放前面（后面LIS就不会同时取到了）。

这样对于envelops的高来说，就是上面的LIS问题了，可以用二分来解。

class Solution {public:    static bool cmp(pair
     
       &a, pair
      
        &b){        if (a.first==b.first) return a.second>b.second;        return a.first
       
        >& envelopes) {        int n=envelopes.size();        sort(envelopes.begin(),envelopes.end(),cmp);                vector
        
          tmp; //store height        for (int i=0;i
         
          tmp.back()){                tmp.push_back(envelopes[i].second);            }else{                int index=lower_bound(tmp,envelopes[i].second);                tmp[index] = envelopes[i].second;            }        }        return tmp.size();    }        int lower_bound(vector
          
            &a, int num){ int low=0, high=a.size(); while (low