Cod sursa(job #3285593)

Utilizator MMEnisEnis Mutlu MMEnis Data 13 martie 2025 11:03:58
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f("scmax.in");
ofstream g("scmax.out");

int v[100001];
int dp[100001];
int pre[100001];
int afisare[100001];

int main()
{
    int n, i, j;
    f >> n;
    for ( i = 1; i <= n; i ++ )
        f >> v[i];
    dp[1] = 1;
    for ( i = 2; i <= n; i ++ )
    {
        for ( j = 1; j < i; j ++ )
            if ( v[i] > v[j] && dp[i] < dp[j] )
            {
                dp[i] = dp[j];
                pre[i] = j;
            }
        dp[i] ++;
    }
    int pmax, maxx = -1;
    for ( i = 1; i <= n; i ++ )
    {
        if ( maxx < dp[i] )
        {
            maxx = dp[i];
            pmax = i;
        }
    }
    g << maxx << '\n';
    i = 1;
    while ( pmax > 0 )
    {
        afisare[i++] = v[pmax];
        pmax = pre[pmax];
    }
    for ( i = i - 1; i > 0; i -- )
        g << afisare[i] << " ";
    return 0;
}