Cod sursa(job #858660)

Utilizator cristitamasTamas Cristian cristitamas Data 19 ianuarie 2013 10:12:28
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <cstdio>
using namespace std;

int n,sir[100005],lg[100005];
int max,ind;

void citire(){
    scanf("%d",&n);
    for(int i=0;i<n;++i)
        scanf("%d",&sir[i]);
}

void rezolvare(){
    for(int i=n-1;i>=0;--i){
        lg[i]=1;
        for(int j=i+1;j<n;++j)
            if(lg[j]+1>lg[i] && sir[j]>sir[i])
                lg[i]=lg[j]+1;
        if(lg[i]>max){
                max=lg[i];
                ind=i;
        }
    }
    printf("%d\n",max);
}

void afisare(){
    printf("%d ",sir[ind]);
    for(int i=ind+1;i<n;++i)
        if(lg[i]==max-1 && sir[i]>sir[ind]){
            max=lg[i];
            ind=i;
            printf("%d ",sir[i]);
        }
}

int main()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    citire();
    rezolvare();
    afisare();
    return 0;
}