Cod sursa(job #2133584)

Utilizator corina_dimitriuDimitriu Corina corina_dimitriu Data 17 februarie 2018 10:19:33
Problema Subsir crescator maximal Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#define NMAX 2000
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int a[NMAX];
int lgmax[NMAX];
int urm[NMAX];
int n;
int main()
{int i,maxim,urmator,j,pozmax;
    fin>>n;
    for(i=0;i<n;i++)
        fin>>a[i];
    //cel mai mic sufux are un element
    lgmax[n-1]=1;
    urm[n-1]=-1;
    for(i=n-2;i>=0;i--)
    {
        maxim=1;
        urmator=-1;
        for(j=i+1;j<n;j++)
            if(a[i]<a[j]&&1+lgmax[j]>maxim)
              {
               maxim=1+lgmax[j];
               urmator=j;
              }
        lgmax[i]=maxim;
        urm[i]=urmator;
    }
    //afisarea
    maxim=lgmax[0];
    pozmax=0;
    for(i=1;i<n;i++)
        if(lgmax[i]>maxim)
        {
            maxim=lgmax[i];
            pozmax=i;
        }
    fout<<maxim<<'\n';
    fout<<a[pozmax];
    while(urm[pozmax]!=-1)
        {
          pozmax=urm[pozmax];
          fout<<" "<<a[pozmax];
        }
    fout<<'\n';
    fin.close();
    fout.close();

    return 0;
}