Cod sursa(job #1015922)

Utilizator cristitamasTamas Cristian cristitamas Data 25 octombrie 2013 14:19:37
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <cstdio>
using namespace std;

int n;
int sir[100005]; //sirul de elemente
int L[100005]; //sirul in care salvam subsirul maximal
int urm[100005];
int ind_max;

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

void rezolvare(){
    L[n-1]=1;
    urm[n-1]=n-1;
    for(int i=n-2;i>=0;--i){
        urm[i]=i;//retine pozitia maximului din secventa i+1,n
        L[i]=0;
        for(int j=i+1;j<n;++j)
            if(sir[i]<sir[j] && L[urm[i]]< L[j])
                urm[i]=j;
        L[i]= L[urm[i]]+1;
        if(L[i]>L[ind_max])
            ind_max=i;
    }
}

void afisare(){
    printf("%d\n",L[ind_max]);
    int i=ind_max;
    while(i!=urm[i]){
        printf("%d ",sir[i]);
        i=urm[i];
    }
    printf("%d ",sir[i]);
}

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