Cod sursa(job #781996)

Utilizator AndupkIonescu Alexandru Andupk Data 25 august 2012 16:19:16
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include<fstream>
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
long v[100000],vpred[100000],vnr[100000];
void afis(int ind)
{
if(vpred[ind]+1)
	afis(vpred[ind]);
	
out<<v[ind]<<" ";
}
int main()
{
int max=1,i,ind,j,n;
in>>n;
for(i=0;i<n;i++)
	in>>v[i];

vpred[0]=-1;
vnr[0]=1;

for(i=1;i<n;i++)
{
  vpred[i]=-1;
  vnr[i]=1;
  for(j=0;j<i;j++)
      if(v[j]<v[i] && vnr[j]>=vnr[i] )
	         {
		       vnr[i]=vnr[j]+1;
			   vpred[i]=j;
			   if(vnr[i]>max)
			    {
			       ind=i;
				   max=vnr[i];
			    }
		     }

}
out<<max<<endl;
afis(ind);
return 0;
}