Cod sursa(job #539940)

Utilizator razvanm1Razvan Mereu razvanm1 Data 23 februarie 2011 15:46:10
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<iostream>

#include<fstream>

using namespace std;

int a[100005],b[100005],s[100005],max1[100005];

int main()
{ int n,i,j,k=0,m=0;
  ifstream fin("scmax.in");
  ofstream fout("scmax.out");
  fin>>n;
  m=0;
  for(i=1;i<=n;i++)
  {
	  fin>>a[i];
	  
  }
  m=0;
  max1[1]=1;
  for(i=2;i<=n;i++)
  {
	for(j=1;j<i;j++)
	{
		if((a[j]<a[i])&&(max1[j]>max1[i]))
		{
			max1[i]=max1[j];
		}
	}
	max1[i]++;
	if(max1[i]>m) m=max1[i];
  }
  fout<<m<<endl;
  k=0;
  for(i=n;i>=1;i--)
  {
	  if(max1[i]==m)
	  {
		  k++;
		  m--;
		  s[k]=a[i];
	  }
  }
  for(i=k;i>=1;i--)
  {
	  fout<<s[i]<<" ";
  }
  fin.close();
  fout.close();
  return 0;
}