Cod sursa(job #2285961)

Utilizator Vlad_NituNitu Vlad-Petru Vlad_Nitu Data 19 noiembrie 2018 16:43:03
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <bits/stdc++.h>
#define NMAX 100010
using namespace std ;
ifstream f ("scmax.in");
ofstream g("scmax.out") ;
long long v[NMAX] ,  L[NMAX] , sol[NMAX] , lmax = 0 , q , N , Max , poz;
int main()
{
    f >> N ;
    for (int i = 1 ; i <= N ; i++)
        f >> v[i] ;
    L[1] = 1;
    lmax = 1 ;
    for (int i = 2 ; i <= N ; i ++)
    {
        Max = 0 ;
        for (int j = i - 1 ; j >= 1 ; --j)
            if (v[j] < v[i] && L[j] > Max)
            Max = L[j];
        L[i] = Max + 1 ;
        if (L[i] > lmax)
        {
            lmax = L[i] ;
            poz = i ;
        }
    }
    q = 1 ;
    sol[1] = v[poz];
    lmax -- ;
    for (int i  = poz - 1 ; i >= 1 ; i -- )
    {
        if (v[i] < sol[q] && L[i] == lmax)
        {
            q++ ;
            sol[q] = v[i];
            lmax -- ;
        }
    }

    g << q << '\n';
    for (int i = q  ; i >= 1 ; i--)
        g << sol[i] << " " ;
    return 0 ;

}