Cod sursa(job #2133578)

Utilizator sunttttareTudor Popescu sunttttare Data 17 februarie 2018 10:17:41
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#define LGMAX 100000

using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");

int a[LGMAX];
int lgmax[LGMAX];
int urm[LGMAX];
int n;

int main()
{
    int i,j,maxim,urmator,pozmax;
    fin>>n;
    for (i=0;i<n;i++)
        fin>>a[i];
    //cel mai mare sufix 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;
        }
    //afisare
    maxim=lgmax[0];
    pozmax=0;
    for (i=1;i<n;i++)
        if (maxim<lgmax[i])
           {
           maxim=lgmax[i];
           pozmax=i;
           }
    fout<<maxim<<'\n';
    fout<<a[pozmax];
    while (urm[pozmax]!=-1)
          {
          pozmax=urm[pozmax];
          fout<<" "<<a[pozmax];
          }
    fout<<'\n';
    fout.close();
    return 0;
}