1 int arr[maxn],ans[maxn],len,n; 2 3 void get_lis() 4 { 5 ///ans为序列数组 6 ans[1] = arr[1]; 7 len=1; 8 for(int i=2; i<=n; ++i){ 9 if(arr[i]>ans[len])///严格上升 10 ans[++len]=arr[i]; 11 else{ 12 int pos=lower_bound(ans,ans+len,arr[i])-ans; 13 ans[pos] = arr[i]; 14 } 15 } 16 } 17 18 int get_lis(int arr[maxn]) 19 { 20 ///ans为序列数组 21 ans[1] = arr[1]; 22 len=1; 23 for(int i=2; i<=n; ++i){ 24 if(arr[i]>ans[len])///严格上升 25 ans[++len]=arr[i]; 26 else{ 27 int pos=lower_bound(ans,ans+len,arr[i])-ans; 28 ans[pos] = arr[i]; 29 } 30 } 31 return len; 32 }