Cod sursa(job #269325)

Utilizator eugen.nodeaEugen Nodea eugen.nodea Data 2 martie 2009 19:44:49
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.61 kb
# include <stdio.h>
# define n 5002
long a[n];
int N,i,j,L[n],P[n],pm,pM;

int main()
{
  freopen("subsir2.in","r",stdin);
  freopen("subsir2.out","w",stdout);
  scanf("%d",&N);
  pM=1;
  for (i=1;i<=N;++i)
     scanf("%ld ",&a[i]);
  L[N]=1; P[N]=-1; pM=N;
  for (i=N-1;i>0;--i){
      P[i]=-1; L[i]=1;
      for (j=i+1;j<=N;++j)
	if (a[i]<=a[j]){
	     if (L[i]<L[j]+1){
		  L[i]=L[j]+1;
		  P[i]=j;
		 }
	     else if ((L[i]==L[j]+1) && a[j]<a[P[i]]) P[i]=j;
	  }
    if (L[i]>L[pM]) pM=i;
  }
  printf("%d\n",L[pM]);
  i=pM;
  while(i!=-1){
    printf("%d ",i);
    i=P[i];
   }
  return 0;
}