Cod sursa(job #3287937)

Utilizator pacelaaaCiurea Pavel pacelaaa Data 19 martie 2025 21:40:01
Problema Subsir crescator maximal Scor 35
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" );

#define cin fin
#define cout fout
#define FR( a, b ) for( a = 0; a < b; a ++)
#define FOR( a, c, b ) for( a = c; a < b; a++)

const int Nmax = 2e5 + 5;

int a[Nmax], dp[Nmax], previous[Nmax];

int main()
{
    int n, maxim, i, j, poz_max;
    cin >> n;
    FOR( i, 1, n + 1 )
      cin >> a[i];

    dp[1] = 1;
    previous[1] = 0;
    FOR( i, 2, n + 1 ) {
      maxim = 1;
      previous[i]= 0;
      FOR( j, 1, i ) {
        if( (a[j] < a[i]) && ( dp[j] + 1 > maxim ) ) {
          maxim = dp[j] + 1;
          previous[i] = j;
        }
      }
      dp[i] = maxim;
    }
    poz_max = 1;
    FOR( i, 1, n + 1 )
      if ( dp[i] > dp[poz_max] )
        poz_max = i;

    cout << dp[poz_max] << '\n';
    do {
      cout << a[poz_max] << " ";
      poz_max = previous[poz_max];
    } while( previous[poz_max] != 0 );

    return 0;
}