Cod sursa(job #191076)

Utilizator slayer4uVictor Popescu slayer4u Data 25 mai 2008 10:23:26
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<stdio.h>
#include<iostream.h>
#define NMAX 100010
int a[NMAX], l[NMAX], succ[NMAX], n, max,i,j,k,pozmax;
void read()
{
 cin>>n;
 for (i=1;i<=n;i++)
  cin>>a[i];
}
int main()
{
 freopen ("scmax.in","rt",stdin);
 freopen ("scmax.out","wt",stdout);
 read();
 l[n]=1;
 succ[n]=-1;
 for (i=n-1;i;i--)
  for (j=i+1,l[i]=1, succ[i]=-1;j<=n;j++)
  {
   if (a[i]<=a[j] && 1+l[j]>l[i])
   {
	l[i]=l[j]+1;
	succ[i]=j;
   }
  }
 max=0;
 pozmax=1;
 for (i=1;i<=n;i++)
  if (l[i]>max)
  {
   max=l[i];
   pozmax=i;
  }
cout<<max<<"\n";
 for (i=pozmax;i!=-1;i=succ[i])
  cout<<a[i]<<" ";
cout<<" ";
 return 0;
}