O(n2)

  1.     int lengthOfLIS(vector<int>& nums) {
  2.         if(nums.empty())return 0;
  3.         int len = nums.size();
  4.         vector<int> dp(len, 0);
  5.         for(int i = 0;i < len;++i){
  6.             int _max = 1;
  7.             for(int j = 0;j < i;++j){
  8.                 if(nums[i] > nums[j])
  9.                     _max = max(dp[j] + 1, _max);
  10.             }
  11.             dp[i] = _max;
  12.         }
  13.         int maxlen = 0;
  14.         for(int n : dp){
  15.             maxlen = max(maxlen, n);
  16.         }
  17.         return maxlen;
  18.     }

二分查找 O(nlogn)

  1.     int lengthOfLIS(vector<int>& nums) {
  2.         if(nums.empty())return 0;
  3.         vector<int> tails(nums.size(), 0);
  4.         int len = 0;
  5.         for(int num : nums){
  6.             int index = binarySearch(num, len, tails);
  7.             tails[index] = num;
  8.             if(index == len)++len;
  9.         }
  10.         return len;
  11.     }
  12.     int binarySearch(int key, int hi, vector<int> &tails){
  13.         int lo = 0, mi = 0;
  14.         while(lo < hi){
  15.             mi = ((hi - lo) >> 1) + lo;
  16.             if(tails[mi] == key)return mi;
  17.             else if(tails[mi] > key)hi = mi;
  18.             else lo = mi + 1;
  19.         }
  20.         return lo;
  21.     }

二分查找问题