Cod sursa(job #1054989)

Utilizator EdyOnuEdy Onu EdyOnu Data 14 decembrie 2013 10:39:24
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <iostream>
using namespace std;
long long v[100000],p[100000],z[100000],n;
ifstream f("secmax.in");
ofstream y("secmax.out");
void citire()
{f>>n;
 for(long long i=1;i<=n;i++)f>>v[i];
 z[v[n]]=1;
 p[v[n]]=0;
}
void subsir(long long v[100000])
{for(long long i=n-1;i>=1;i--)
  {long long d=1,h=0,max=0,j;
   for(j=i+1;j<=n;j++)
   if(v[j]>v[i])
    {max=z[v[j]]+1;
     if(max>d&&h<j)
     {d=max;
      h=j;
     }
    }
    z[v[i]]=d;
    p[v[i]]=h;
  }
}
void maximul(long long z[100000],long long&d,long long&g)
{ d=0;
 for(long long i=1;i<=n;i++)
    if(z[v[i]]>d)
    {d=z[v[i]];
     g=i;
    }

}
long long x[100000];
void afisare(long long p[100000],long long v[100000])
{long long i=1,d=0,g=0;
 maximul(z,d,g);
 y<<d<<endl;
 y<<v[g]<<" ";
 long long max=g;
 for(i=1;i<=n;i++)
  if(v[p[v[i]]]!=0&&x[v[p[v[i]]]]==0&&p[v[i]]>max)
  {y<<v[p[v[i]]]<<" ";
    x[v[p[v[i]]]]=1;
   max=p[v[i]];
  }
}
int main()
{citire();
 subsir(v);
 afisare(p,v);
    return 0;
}