Cod sursa(job #3265017)

Utilizator Alexbora13Bora Ioan Alexandru Alexbora13 Data 26 decembrie 2024 15:29:23
Problema Subsir crescator maximal Scor 55
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.63 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 100000;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

int n;
int v[NMAX+1];
int dp[NMAX+1];
int maxi, ind, ant[NMAX+1];

void rez(int x)
{
    if(ant[x] != 0)rez(ant[x]);
    fout << v[x] << ' ';
}

int main()
{
    fin >> n;
    for(int i=1; i<=n; i++)
        fin >> v[i];
    dp[1] = 1;
    for(int i=2; i<=n; i++)
    {
        for(int j=1; j<i; j++)
            if(v[j] < v[i] && dp[j]+1 > dp[i])
                dp[i] = dp[j]+1, ant[i] = j;
        if(dp[i] > maxi)
            maxi = dp[i], ind = i;
    }   
    fout << maxi+1 << '\n';
    rez(ind);
    return 0;
}