Pagini recente » Cod sursa (job #2885346) | Cod sursa (job #1915456) | Cod sursa (job #2740585) | Rating FMI - Dumea Eduard Constantin (costel93) | Cod sursa (job #931290)
Cod sursa(job #931290)
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100100;
int n, x[N], norm[N], anter[N];
int arb[N];
struct scmax
{
int v,ant;
}t[N];
int mx;
void citire()
{
freopen("scmax.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&x[i]);
norm[i]=x[i];}
fclose(stdin);
}
int binary(int v, int st , int dr)
{
if(st==dr)
if(anter[st]==v)
return st;
else return -1;
int m=(st+dr)/2;
if(anter[m]==v)
return m;
if(v<anter[m])
return binary(v,st,m-1);
return binary(v,m+1,dr);
}
void normalizare()
{
int k=0,ant=0;
for(int i=1;i<=n;++i)
{
if(norm[i]!=ant)
k++,ant=norm[i];
anter[k]=norm[i];
}
for(int i=1;i<=n;++i)
norm[i]=binary(x[i],1,n);
}
void solve()
{
for(int j=1;j<=n;++j)
for(int i=0;i<norm[j];++i)
if(t[i].v+1>t[norm[j]].v){
t[norm[j]].v=t[i].v+1,t[norm[j]].ant=i;
if(t[norm[j]].v>t[mx].v)
mx=norm[j];
}
}
void print(int p)
{
if(t[p].ant!=0)
print(t[p].ant);
printf("%d ",anter[p]);
}
void afisare()
{
freopen("scmax.out","w",stdout);
printf("%d\n",t[mx].v);
int k=mx;
print(k);
fclose(stdout);
}
int main()
{
citire();
sort(norm+1,norm+1+n);
normalizare();
solve();
afisare();
return 0;
}