Cod sursa(job #1695753)

Utilizator eden001Muntean Natan eden001 Data 27 aprilie 2016 19:09:56
Problema Subsir crescator maximal Scor 45
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <stdio.h>

using namespace std;
int n,v[100000],maxim,max1,k,i,j,c[100000];
void afisare(int x){
    if(c[x]>=1){
        int z=x;
        while(c[z]!=c[x]-1&&v[z]>=v[x])z--;
        afisare(z);
        printf("%d ",v[x]);}
}

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]);
        maxim=0;
        for(j=i;j>=1;j--){
            if(c[j]>maxim&&v[j]<v[i])maxim=c[j];
        }
        c[i]=maxim+1;
        if(max1<=maxim){
            k=i;
            max1=maxim;
        }
    }
    printf("%d\n",c[k]);
    afisare(k);
    printf("\n");
}