Pagini recente » Borderou de evaluare (job #1036583) | Cod sursa (job #1216850) | Cod sursa (job #1901539) | Cod sursa (job #1263340) | Cod sursa (job #1826425)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int lmax[1000],urm[1000],maxi,n,i,j,pmax,a[1000];
///a-vectorul initial
///lmax[i]-este lungimea sirului maximal ce se poate forma pornind de la elem i
///urm[i]-este pozitia urmatorului elem dupa a[i] care apare in sirul de lungime maximala
int main()
{ f>>n;
for(i=1;i<=n;i++)
f>>a[i];
lmax[n]=1;
urm[n]=-1;
for(i=n-1;i>=1;i--)
{maxi=0;pmax=-1;
for(j=i+1;j<=n;j++)///daca nu pun egal obtin prima solutie, daca pun egal o obtin pe ultima, ambele fiind optime
if(a[i]<a[j]&&lmax[j]>=maxi){maxi=lmax[j];pmax=j;}
///Daca punem >= obtinem cel mai lung subsir descrescator de lungime maxima
lmax[i]=1+maxi;urm[i]=pmax;
}
pmax=1;
maxi=lmax[1];
for(i=2;i<=n;i++)
if(lmax[i]>maxi){maxi=lmax[i];pmax=i;}
g<<maxi<<'\n';
for(i=pmax;i!=-1;i=urm[i])
g<<a[i]<<" ";
}