Cod sursa(job #2159122)

Utilizator nicolaefilatNicolae Filat nicolaefilat Data 10 martie 2018 19:17:49
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#define MAXN 100005

using namespace std;

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

int dp[MAXN],v[MAXN],n;

void cit(){
    in>>n;
    for(int i = 1; i <= n; i++)
        in>>v[i];
}
void rez(){
    for(int i = 1; i <= n; i++)
        dp[i] = 1;
    int maxim = 1;
    for(int i = n; i >= 1; i --){
        for(int j = i+1; j <= n; j++){
            if(v[i] < v[j]){
                dp[i] = max(dp[j]+1,dp[i]);
                maxim = max(maxim,dp[i]);
            }
        }
    }
    out<<maxim<<"\n";
    int aux = maxim;
    for(int i = 1; i <= n; i++){
        if(dp[i] == aux && maxim){
            out<<v[i]<<" ";
            aux--;
        }

    }
}



int main()
{
    cit();
    rez();
    return 0;
}