题解 | #最长上升子序列(一)#

很对人讲了二分的过程，但没有讲为什么，我搜了一些用自己的话描述出来，有不恰当的地方请见谅。
新建一个 low 数组，low中的数组有序，且都是low数组最后数插入后目的数组最小值，这样才能发现最长的子序列。
例如：1 4 7 2 5 9 10 3 的最短子序列为 1 4 7 9 10 或 1 2 5 9 10 或 1 4 5 9 10，low数组就为1 2 3 9 10
更新过程如下：

    A[1] = 1，把1放进B[1]，此时B[1] = 1，B[ ] = {1}，len = 1

   A[2] = 4，把4放进B[2]，此时B[2] = 4，B[ ] = {1,4}，len = 2

   A[3] = 7，把7放进B[3]，此时B[3] = 7，B[ ] = {1,4,7}，len = 3

   A[4] = 2，因为2比4小，所以把B[2]中的4替换为2，此时B[ ] = {1,2,7}，len = 3

   A[5] = 5，因为5比7小，所以把B[3]中的7替换为5，此时B[ ] = {1,2,5}，len = 3

   A[6] = 9，把9放进B[4]，此时B[4] = 9，B[ ] = {1,2,5,9}，len = 4

   A[7] = 10，把10放进B[5]，此时B[5] = 10，B[ ] = {1,2,5,9,10}，len = 5

   A[8] = 3，因为3比5小，所以把B[3]中的5替换为3，此时B[ ] = {1,2,3,9,10}，len = 5

C语言代码：

int Index(int *, int, int);

int LIS(int* arr, int arrLen ) {
    // write code here
    if(arrLen <= 1) return arrLen;
    int low[arrLen];
    low[0] = arr[0];
    int len = 1;
    for(int il = 0, ia = 1; ia != arrLen;ia++){
        if(low[il] < arr[ia]){
            low[++il] = arr[ia];
            len++;
        }else{
            int index = Index(low, il, arr[ia]);
            low[index] = arr[ia];
        }
    }
    return len;
}

int Index(int *arr, int il, int target){
    int lo = 0, hi = il;
    while(lo < hi){
        int mid = lo + (hi - lo)/2;
        if(arr[mid] >= target){
            hi = mid;
        }else{
            lo = mid + 1;
        }
    }
    return lo;
}