Cod sursa(job #2133581)

Utilizator Andrei0308Andrei Loghin Andrei0308 Data 17 februarie 2018 10:18:48
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#define NMAX 100000

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, j, maxim, urmator, pozmax;

    fin>>n;

    for(i=0; i < n; i++)
        fin>>a[i];
//cel mai mic 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(lgmax[i] > maxim)
        {
            maxim = lgmax[i];
            pozmax = i;
        }

    fout<<maxim<<endl;

    fout<<a[pozmax]<<" ";

    while(urm[pozmax] != -1)
    {
        pozmax = urm[pozmax];
        fout<<a[pozmax]<<" ";
    }

    fout.close();
    return 0;
}