最长上升子序列LIS

描述

给定一个长度为 n 的数组 arr，求它的最长严格上升子序列的长度。
所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。例如 [1,5,3,7,3] 数组，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。

。
数据范围： 0 <= n <= 1000
要求：时间复杂度 O(n^2)，空间复杂度 O(n)

示例1

输入：[6,3,1,5,2,3,7]
返回值：4
说明：该数组最长上升子序列为 [1,2,3,7] ，长度为4

思路

维护一个伪上升子序列，遍历数组中每一个值，二分找到伪上升子序列中第一个比它大的值，然后将其替换掉，如果没有则直接插入到伪上升子序列最后。

代码

1. 手写二分

       int LIS(vector<int>& arr) {
       // write code here
       int ans = 0;
       int n = arr.size();
       int b[n];
       int lb, rb;
       lb = rb = 0;
       int l, r, mid;
       for(int i=0;i<n;i++){
           l = lb;
           r = rb;
           while(l<r){
               mid = (l+r)/2;
               if(b[mid]>arr[i]) r = mid;
               else l = mid+1;
           }
           if(l>=lb&&l<=rb-1) b[l] = arr[i];
           else b[rb++] = arr[i];
       }
       return rb-lb;
   }
   }

2. upper_bound

   upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

   lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

       int LIS(vector<int>& a) {
       // write code here
       int n = a.size();
       vector<int> b;
       for(int i=0;i<n;i++){
           int p = upper_bound(b.begin(), b.end(),a[i])-b.begin();
           if(p==b.size()) b.push_back(a[i]);
           else b[p] = a[i];
       }
       return b.size();
   }