Cod sursa(job #1871795)

Utilizator AcuasPopescu Nicolae-Aurelian Acuas Data 7 februarie 2017 17:42:27
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <iostream>
#include <fstream>
#define NMAX 100005
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int n,i,j;
long long v[NMAX],c[NMAX],MAX=0,sol[NMAX],poz;
int main(){
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    c[n]=1;
    sol[n]=-1;
    for(i=n-1;i>=1;i--){
        c[i]=1;
        sol[i]=-1;
        for(j=i+1;j<=n;j++)
            if(v[i]<v[j]&&c[i]<c[j]+1){
                c[i]=c[j]+1;
                sol[i]=j;
            }
    }
    MAX=0;
    for(i=1;i<=n;i++){
        if(MAX<c[i]){
            MAX=c[i];
            poz=i;
        }
    }
    g<<MAX<<'\n';
    for(i=1;i<=MAX;i++){
        g<<v[poz]<<' ';
        poz=sol[poz];
    }
    return 0;
}