Cod sursa(job #3252190)

Utilizator Alexbora13Bora Ioan Alexandru Alexbora13 Data 28 octombrie 2024 19:47:31
Problema Subsir crescator maximal Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 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], pos[NMAX+1];

int main()
{
    fin >> n;
    for(int i=1; i<=n; i++)
        fin >> v[i], pos[i] = -1;
    dp[1] = 1;
    for(int i=2; i<=n; i++)
    {
        for(int j=1; j<=i; j++)
        {
            if(v[i] > v[j])
                if(dp[j]+1 > dp[i])
                    dp[i] = dp[j]+1, pos[i] = j;
        }
    }  
    vector <int> ans;
    int p = n;
    while(p != -1)
    {
        ans.push_back(v[p]);
        p  = pos[p];
    } 
    fout << ans.size() << '\n';
    reverse(ans.begin(), ans.end());
    for(int x : ans)
        fout << x << ' ';
    return 0;
}