Pagini recente » Cod sursa (job #85353) | Cod sursa (job #1063790) | Cod sursa (job #1613786) | Cod sursa (job #2289947) | Cod sursa (job #895477)
Cod sursa(job #895477)
//subsir crescator maximal.
//determinati un subsir a lui a crescator
//a[i1]<=a[i2]<=...<=a[ik];
//de lungime maxima
//a(a1,a2,...,an)
//subsir a[i1],a[i2],...a[ik], i1<i2<...<ik
//subsecventa-formata din elmente consecutive. a[i],a[i+1],a[i+k];
#include <fstream>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
//subprobleme. sa se det cel mai lung subsir crescator care incepe la pozitia i;
///notam lgmax[i]= lung celui mai lung subsir cresc.
//urm[i]=pozitia elem care urmeaza dupa a[i] in cel mai lung subsir cresc.
//-1 daca nu exista urmatorul.
int n,i,a[100010],urm[100010],lgmax[100010],maxim,j,jmax;
int main()
{
fin >> n;
for(i=1;i<=n;i++)
fin >> a[i];
lgmax[n]=1;
urm[n]=-1;
for(i=n-1;i>=1;i--)
{
maxim=0;jmax=0;
for(j=i+1;j<=n;j++)
if(a[i]<a[j])
if(lgmax[j]>maxim)
maxim=lgmax[j],jmax=j;
lgmax[i]=1+maxim;
if(jmax!=0)
urm[i]=jmax;
else urm[i]=-1;
}
maxim=0;
for(i=1;i<=n;i++)
if(lgmax[i]>maxim)
maxim=lgmax[i],jmax=i;
fout << maxim << '\n';
int x;
x=jmax;
for(i=1;i<=maxim;i++)
{
fout << a[x] << ' ';
x=urm[x];
}
return 0;
}