Cod sursa(job #2133571)

Utilizator IulianCruduIulian Crudu IulianCrudu Data 17 februarie 2018 10:15:51
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <bits/stdc++.h>
#define NMAX 1000001
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int a[NMAX],lgmax[NMAX],urm[NMAX],n,nrmax,pozmax;
int main()
{
    fin>>n;
    for(int i=0; i<n; i++)
        fin>>a[i];
    // cel mai mic sufix are un element
    lgmax[n-1] = 1;
    urm[n-1] = -1;
    for(int i=n-2; i>=0; i--)
    {
        int maxim = 1;
        int urmator = -1;
        for(int j=i+1; j<n; j++)
            if(a[i]<=a[j] && 1+lgmax[j]>maxim)
            {
                maxim = lgmax[j] + 1;
                urmator = j;
            }
        lgmax[i] = maxim;
        urm[i] = urmator;
        if(nrmax < lgmax[i])
        {
            nrmax = lgmax[i];
            pozmax = i;
        }
    }
    //afisare
    fout<<nrmax<<'\n';
    int i=pozmax;
    while(i != -1)
    {
        fout<<a[i]<<" ";
        i = urm[i];
    }
    fout<<'\n';
    fout.close();
    return 0;
}