Cod sursa(job #3335288)

Utilizator Coman_DianaComan Diana Coman_Diana Data 22 ianuarie 2026 10:53:22
Problema Subsir crescator maximal Scor 45
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <stdio.h>
#include <iostream>

using namespace std;

#define NMAX 100000

int vec[NMAX + 1];
int dp[NMAX + 1];

int main()
{
    FILE *fin, *fout;
    int num_n, ind, ind1, maxi, lmax, poz, cnt, ant;

    fin = fopen( "scmax.in", "r" );
    fscanf( fin, "%d", &num_n );

    for ( ind = 1; ind <= num_n; ind++ )
        fscanf( fin, "%d", &vec[ind] );
    fclose( fin );

    lmax = -1;
    for ( ind = 1; ind <= num_n; ind++ ) {

        maxi = 0;
        for ( ind1 = ind - 1; ind1 >= 1; ind1-- ) {
            if ( vec[ind1] < vec[ind] ) {
                if ( dp[ind1] > maxi )
                    maxi = dp[ind1];
            }
        }
        dp[ind] = 1 + maxi;
        if ( dp[ind] > lmax ) {
            lmax = dp[ind];
            poz = ind;
        }

    }

    for ( ind = 1; ind <= num_n; ind++ )
        dp[ind] = 0;

    ind = 1;
    dp[ind] = ant = vec[poz];
    ind++;
    poz--;
    cnt = lmax - 1;
    while ( cnt > 0 && poz >= 1 ) {

        if ( ant > vec[poz] ) {
            dp[ind] = vec[poz];
            ant = vec[poz];
            ind++;
            cnt--;
        }
        poz--;

    }

    fout = fopen( "scmax.out", "w" );
    fprintf( fout, "%d\n", lmax );
    for ( ind1 = ind - 1; ind1 >= 1; ind1-- )
        fprintf( fout, "%d ", dp[ind1] );
    fclose( fout );


    return 0;
}