Cod sursa(job #2517536)

Utilizator cristianabalcanuCristiana Balcanu cristianabalcanu Data 3 ianuarie 2020 18:17:41
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 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];

FILE* pfin;
FILE* pfout;

int main()
{
    pfin = fopen("scmax.in", "r");
    pfout = fopen("scmax.out", "w");


    fscanf(pfin, "%d", &n);
    // fin >> n;
    for ( int i = 1 ; i <= n ; i++ )
    {
        // fin >> v[i];
        fscanf(pfin, "%d", &(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;
    fprintf(pfout, "%d\n", mx);
    for ( int i = 1 ; i <= mx ; i++ )
    {
        // fout << v[p] << " ";
        fprintf(pfout, "%d ", v[p]);
        p = urm[p];
    }
    return 0;
}