Cod sursa(job #3260809)

Utilizator Alexbora13Bora Ioan Alexandru Alexbora13 Data 3 decembrie 2024 19:06:31
Problema Subsir crescator maximal Scor 55
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 100000;

int n;
int v[NMAX+1];
int dp[NMAX+1];
int pos[NMAX+1], posmax, maxi=INT_MIN;

void show(int ind)
{
    if(pos[ind] != 0)show(pos[ind]);
    fout << v[ind] << ' ';
}

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, pos[i] = j;
        }
        if(dp[i] > maxi)
            maxi = dp[i], posmax = i;
    }
    fout << maxi+1 << '\n';
    show(posmax);
    return 0;
}