https://leetcode.com/problems/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.

nlogn的最长上升子序列～～

二分找的是大于等于的最小值（这个具体看题目意思～）

终于自己写对二分啦

class Solution {
public:
    int s[100000];
    int bi_search(int x, int l, int r) {
        while(l < r) {
            int mid = (l + r)/2;
            //printf("l=%d,r=%d,mid=%d,s[mid]=%d\n",l,r,mid,s[mid]);
            if(s[mid] >= x)
                r = mid;
            else
                l = mid + 1;
        }
        return r;
    }
    int lengthOfLIS(vector<int>& nums) {
        if (nums.size() == 0)
            return 0;
        int tot = 0;
        s[tot] = nums[0];
        for (int i = 1; i < nums.size(); i ++) {
            if (nums[i] > s[tot]) {
                s[++tot] = nums[i];
            } else {
                int pos = bi_search(nums[i], 0, tot);//lower_bound(s, s+tot, nums[i])-s;
                //printf("pos=%d,tot=%d,i=%d,nums[i]=%d\n",pos,tot,i,nums[i]);
                s[pos] = nums[i];
            }
        }
        return tot+1;
    }
};