Cod sursa(job #809058)
#include <fstream>
#define NMAX 1001
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n, a[NMAX], lgmax[NMAX], maxim, sol, urm[NMAX], poz_curenta;
//lgmax[i] reprezinta lungimea celui mai lung subsir crescator care incepe cu a[i]
//pozitia elementului care urmeaza dupa a[i] in cel mai lung subsir crescator
void citire();
void programare_dinamica();
void afisare();
int main()
{
citire();
programare_dinamica();
afisare();
return 0;
}
void citire()
{
int i;
fin>>n;
for(i=1; i<=n; i++)
fin>>a[i];
}
void programare_dinamica()
{
int i, j;
lgmax[n]=1; //initial lgmax[n] are valoarea 1 deoarece doar un subsireul are un singur element si anume a[n]
urm[n]=-1;//initial urm[n] are valoarea -1 deoarece nu urmeaza nimeni dupa a[i]
maxim=1;//maximul initial are valoarea 1
poz_curenta=n;//pornim de la sfarsitul vectorului pentru a face relatia de recurenta butom up
for(i=n-1; i>=1; --i)
{//parcurg vectorul a de la sfarsit la inceput
lgmax[i]=1; urm[i]=-1;
for(j=i+1; j<=n; j++)//parcurgem a si de la i+1 pentru a verifica daca se poate forma un subsir
if(a[i]<a[j] && lgmax[i]<lgmax[j]+1)//daca se poate forma un subsir cu elementele de pe poz a[i] si a[j]
{
lgmax[i]=lgmax[j]+1;
urm[i]=j;
if(lgmax[i]>maxim)
{ maxim=lgmax[i];
poz_curenta=i;//actualizam pozitia curenta cu i
}
}
}
}
void constr()
{
int i;
i=poz_curenta;
while(i!=-1)
{
fout<<a[i]<<' ';
i=urm[i];
}
}
void afisare()
{
fout<<maxim<<'\n';
constr();
fout.close();
}