Cod sursa(job #2500417)

Utilizator Tudor_Trasculescu123Tudor Trasculescu Tudor_Trasculescu123 Data 27 noiembrie 2019 20:57:53
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>
#define NMAX 100005

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

int n, maxim, v[NMAX], max_length[NMAX], poz[NMAX] ;

void read()
{
    fin >> n ;
    for(int i=1; i<=n; i++)
        fin >> v[i] ;
}

void create()
{
    int x, y ;
    for(int i=n; i>=1; i--)
    {
        x = 0 ;
        y = 1 ;
        for(int j=i+1; j<=n; j++)
            if(v[j] > v[i] && max_length[j] + 1 > y)
            {
                x = j ;
                y = max_length[j] + 1;
            }
        max_length[i] = y ;
        if(maxim < max_length[i])
            maxim = max_length[i] ;
        poz[i] = x ;
    }
}

void afis()
{
    int y ;
    fout << maxim << "\n" ;
    for(int i=1; i<=n; i++)
        if(max_length[i] == maxim)
        {
            y = i ;
            break ;
        }
    while(poz[y] != 0)
    {
        fout << v[y] << " " ;
        y = poz[y] ;
    }
    fout << v[y] ;

}

int main()
{
    read() ;
    create() ;
    afis() ;

    return 0;
}