Cod sursa(job #181262)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 18 aprilie 2008 09:28:01
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <stdio.h>
#define INF 10000000
int main(){
	int n,v[5001],i,j,p[5001],l[5001]={0},min,poz,lmax,pozmax;
	freopen("subsir2.in","r",stdin);
	freopen("subsir2.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&v[i]);
	l[n]=1;
	for(i=n-1;i>=1;--i){
		min=INF;
		poz=0;
		for(j=i+1;j<=n;j++)
			if(v[j]>=v[i] && v[j]<=min && l[j]>=l[i]){
				min=v[j];
				poz=j;
				l[i]=l[j];
			}
		p[i]=poz;
		l[i]++;
		if(l[i]>lmax){
			lmax=l[i];
			pozmax=i;
		}
		else if(l[i]==lmax) 
			if(v[i]<v[pozmax])
				pozmax=i;
	}
	printf("%d\n",lmax);
	while(lmax){
		printf("%d ",pozmax);
		lmax--;
		pozmax=p[pozmax];
	}
	return 0;
}