首页 > 代码库 > 二分求最长单调递增子序列并输出最长的序列(模板)
二分求最长单调递增子序列并输出最长的序列(模板)
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 }
二分求最长单调递增子序列并输出最长的序列(模板)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。