首页 > 代码库 > 二分求最长单调递增子序列并输出最长的序列(模板)

二分求最长单调递增子序列并输出最长的序列(模板)

 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #define N 100005 6 using namespace std; 7 int num[N]; 8 int a[N]; 9 int pre[N];10 int pos[N];11 12 void print(int x){13     if(x==0) return;14     print(pre[x]);15     cout<<num[x]<<" ";16 }17 18 int main(){19     int n;20     while(cin>>n){21         memset(a, 0x3f, sizeof(a));22         int len = 0;23         for(int i=1; i<=n; ++i){24             cin>>num[i];25             int ll = lower_bound(a, a+len, num[i]) - a;26             if(ll+1 > len) len = ll+1;27             a[ll] = num[i];//第ll个位置新插入的数字num[i] 28             pos[ll] = i;//第ll个位置插入的是第i个数字 29             if(ll-1>=0) pre[i] = pos[ll-1];//当前插入的第i个数字的在递增序列中的前一个数字是第几个! 30         }31         print(pre[pos[len-1]]);32         cout<<(num[pos[len-1]])<<endl;33         cout<<len<<endl;34     }35     return 0;36 } 

 

二分求最长单调递增子序列并输出最长的序列(模板)