Cod sursa(job #167945)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 30 martie 2008 14:05:30
Problema Subsir 2 Scor 14
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <stdio.h>

long n,i,j,a[5005],l[5005],t[5005],min,max;
long mark[5005],p;

void afisare(long x){
     if (x){
        afisare(t[x]);
     }
     else return;
     printf("%ld ",x);
}

int main(){
    freopen("subsir2.in","r",stdin);
    freopen("subsir2.out","w",stdout);
    
    scanf("%ld",&n);
    for (i=1;i<=n;i++)
        scanf("%ld",&a[i]);
    
    l[1]=1;
    for (i=2;i<=n;i++){
        max=0;
        for (j=1;j<i;j++)
            if (a[j]<a[i]){
               mark[j]=1;
               if (l[j]>max){max=l[j];p=j;}
               else if (max==l[j])
                       if (a[j]<a[p])p=j;
            }
        l[i]=max+1;
        t[i]=p;
    }
    min=n+1;
    
    for (i=1;i<=n;i++)
        if (!mark[i])
           if (l[i]<min){min=l[i];p=i;}
           else if (l[i]==min)
                   if (a[i]<a[p])p=i;
    
    afisare(p);
    printf("\n");

return 0;
}