Cod sursa(job #384141)

Utilizator bora_marianBora marian bora_marian Data 19 ianuarie 2010 11:53:39
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include<fstream>
using namespace std;
int v[100005],l[100005],p[100005],n;
int main()
{
	ifstream fin("scmax.in");
	fin>>n;
	int q;
	for(q=1;q<=n;q++)
	  fin>>v[q];
	 l[n]=1;
	 p[n]=-1;
	 for(q=n-1;q>0;--q)
	 {
		int poz=0;
		for(int j=q+1;j<=n;j++)
		  if(v[q]<v[j])
			 { if(poz==0)
			     poz=j,p[q]=poz;
			 else
			  if(l[poz]<=l[j])
			   poz=j,p[q]=poz;}
			if(poz==0)
			  l[q]=1,p[1]=-1;
			else
			  l[q]=l[poz]+1;
		}
 ofstream fout("scmax.out");
 int poz=1;
 for(int q=2;q<=n;q++)
   if(l[q]>l[poz])
     poz=q;
fout<<l[poz]<<endl;
 q=poz;
while(q!=-1)
 {
	 fout<<v[q]<<" ";
	 q=p[q];
	} 	 			       	    
return 0;
}