Cod sursa(job #1857718)

Utilizator mirceagavrizimircea luca gavrizi mirceagavrizi Data 26 ianuarie 2017 16:08:29
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<iostream>
int v[100000],d[100000],k[100000];
#include<stdio.h>
using namespace std;
int main(){
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    int n,i,j,maxx,g;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>v[i];
    for(i=2;i<=n;i++){
        maxx=-1;
        for(j=i-1;j>=1;j--){
            if(v[j]<v[i]){
                if(d[j]>maxx)
                    maxx=d[j];
            }
        }
        d[i]=maxx+1;
    }
    maxx=-1;
    for(i=1;i<=n;i++){
        if(d[i]>maxx)
            maxx=d[i];
    }
    cout<<maxx+1<<endl;
    g=maxx;
    j=1;
    for(i=n;i>=1;i--){
        if(d[i]==g){
            g--;
            k[j]=v[i];
            j++;
        }
    }
    for(i=j-1;i>=1;i--)
        cout<<k[i]<<" ";
return 0;
}