Cod sursa(job #2474919)
Utilizator | Greenio Greely greelio | Data | 15 octombrie 2019 22:55:37 |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.66 kb |
#include<bits/stdc++.h>
#define N 100010
using namespace std;
int s[N], p[N];
int n,a[N],k ;
void rec(int x) {
if (!x) return;
rec(p[x]);
cout<<a[x]<<" ";
}
int main() {
ifstream cin("scmax.in");
freopen("scamax.out", "w", stdout);
cin>>n;
for (int i=1; i<=n; i++) cin>>a[i];
s[1]=k=1;
for(int i=2; i<=n; i++) {
int st=1,dr=k;
while (st<=dr) {
int mid=(st+dr)>>1;
if (a[s[mid]]<a[i]) st=mid+1;
else dr=mid-1;
}
if (st>k) k = st;
s[st] = i;
p[i] = s[st-1];
}
cout<<k<<'\n';
rec(s[k]);
return 0;
}