Cod sursa(job #808815)

Utilizator popacamilpopa camil popacamil Data 7 noiembrie 2012 13:35:44
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<cstdio>
using namespace std;

int v[100005],lg[100005],lgmax,urm[100005],i,j,n,pozlgmax;

int main(){

    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);

    scanf("%d",&n);

    for(i=1;i<=n;++i){

        scanf("%d",&v[i]);

    }

    lg[n]=1;
    lgmax=1;
    urm[n]=-1;
    for(i=n-1;i>=1;--i){
        lg[i]=1;
        urm[i]=-1;
        for(j=i;j<=n;++j){
            if(lg[j]==lgmax && v[i]<v[j]){

                lg[i]=lgmax+1;
                ++lgmax;
                pozlgmax=i;
                urm[i]=j;

            }

        }

    }

    printf("%d\n",lgmax);

    for(i=pozlgmax;urm[i]!=-1;){

        printf("%d ",v[i]);
        i=urm[i];
    }
    printf("%d",v[i]);
    return 0;

}