Cod sursa(job #781991)

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

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

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

}
out<<max<<endl;
j=0;
while(vpred[ind])
{
a[j]=v[ind];
ind=vpred[ind];
j++;
}
out<<v[ind]<<" ";
for(i=max-2;i>=0;i--)
	out<<a[i]<<" ";
return 0;
}