Cod sursa(job #203023)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 12 august 2008 20:33:07
Problema Subsir 2 Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<stdio.h>
#include<stdlib.h>
#define NMAX 5000

int n,a[NMAX+1];
int l[NMAX+1],next[NMAX+1];


int main(){
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
int i,j,lmin,lmax,first;
char sir[NMAX*11],*p;
scanf("%d\n",&n);
//for(i=1;i<=n;++i) scanf("%d",&a[i]);
fgets(sir,NMAX*11,stdin);p=sir;
for(i=1;i<=n;++i){
	a[i]=atoi(p);
	while(*p!=32) ++p;
	++p;
	}
l[n]=1;
for(i=n-1;i;--i){
	lmax=0;
	for(j=i+1;j<=n;++j)
		if(a[i]<=a[j])
			if(l[j]>lmax){
				lmax=l[j];next[i]=j;
				}
			else{
				if(l[j]==lmax)
					if(a[j]<a[next[i]])
						next[i]=j;
				}

	l[i]=lmax+1;
	}
lmax=0;
for(i=1;i<=n;++i)
	if(lmax<l[i]) {lmax=l[i];first=i;}

lmin=lmax;
printf("%d\n",lmin);
i=first;
while(next[i]){
	printf("%d ",i);
	i=next[i];
	}
printf("%d",i);
return 0;
}