Cod sursa(job #1458655)

Utilizator tiby10Tibi P tiby10 Data 8 iulie 2015 11:26:07
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
//scmax
#include<bits/stdc++.h>
#define debug cerr<<"ok";
#define MAXN 100000
using namespace std;

int n,i,j,a[MAXN],best[MAXN],child[MAXN],celMaiTheBest,indexM;

void drum(){

while(celMaiTheBest){
printf("%d ",a[indexM]);
indexM=child[indexM];
celMaiTheBest--;
}

}


int main ()
{
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    scanf("%d",&n);

    int maX=0,index=0;

    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    best[n]=1;
    for(i=n-1;i>=1;i--,maX=0){
            child[i]=-1;
        for(j=i+1;j<=n;j++)
            if(best[j] > maX && a[i] < a[j]){
                maX=best[j];
                child[i]=j;
            }

        best[i]=maX+1;
        if(best[i] > celMaiTheBest){
            celMaiTheBest=best[i];
            indexM=i;
        }
    }

        printf("%d\n",celMaiTheBest);
        drum();
    return 0;
}