题目描述：

给定一个整型数组， 求这个数组的最长严格递增子序列的长度。 譬如序列1 2 2 4 3 的最长严格递增子序列为1，2，4或1，2，3.他们的长度为3。

 

思路

1. 朴素求解 LIS, 没什么可说的

2. 又涉及到二分查找, 这次找的是大于等于 target 的最小值. = 时直接返回, 这就简单了. low > high 时, 返回 low, 因为上一轮比较, mid < target

 

 

代码

#include 
     
      #include 
      
       using namespace std;int arr[100010];int record[100010];int search(int x, int low, int high) {    if(low > high) {        return low;    }    int mid = (low+high)>>1;    if(record[mid] == x) {        return mid;    }else if(record[mid] > x) {        return search(x, low, mid-1);    }else{        return search(x, mid+1, high);    }}int main() {//    freopen("testcase.txt", "r", stdin);    int n;    while(scanf("%d", &n) != EOF) {        for(int i = 0; i < n; i ++)             scanf("%d", &arr[i]);        record[0] = arr[0];        int len = 1;        for(int i = 1; i < n; i ++) {            if(arr[i] > record[len-1]) {                record[len] = arr[i];                len++;            }else{                int insertPos = search(arr[i], 0, len-1);                record[insertPos] = arr[i];            }        }        printf("%d\n", len);    }    return 0;}