Cod sursa(job #2517527)

Utilizator cristianabalcanuCristiana Balcanu cristianabalcanu Data 3 ianuarie 2020 18:06:53
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin ("scmax.in");
ofstream fout ("scmax.out");
int v[100003];
int n;
int lmax[100003], urm[100003];
int main()
{
    fin >> n;
    for ( int i = 1 ; i <= n ; i++ )
        fin >> v[i];
    int u, nr;
    for ( int i = n ; i >= 1 ; i-- )
    {
        u = -1;
        nr = 0;
        for ( int j = i + 1 ; j <= n ; j++ )
        {
            if ( v[i] < v[j] )
            {
                if ( nr < lmax[j] )
                {
                    nr = lmax[j];
                    u = j;
                }
            }
        }
        urm[i] = u;
        lmax[i] = nr + 1;
    }
    int mx = 0, p;
    for ( int i = 1 ; i <= n ; i++ )
    {
        if ( mx < lmax[i] )
        {
            mx = lmax[i];
            p = i;
        }
    }
    fout << mx << endl;
    for ( int i = 1 ; i <= mx ; i++ )
    {
        fout << v[p] << " ";
        p = urm[p];
    }
    return 0;
}