Cod sursa(job #539876)

Utilizator krysstynelBojor Fineas Cristian krysstynel Data 23 februarie 2011 14:14:19
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<fstream>
using namespace std;
int a[100001],b[100001];
int main()
{
	ifstream fi("scmax.in");
	ofstream fo("scmax.out");
	
	int n,poz,max,i,j,maxb=0,pozb=0;
	
	fi>>n;
	
	for(i=0; i<n; i++)
		fi>>a[i];
	
	b[n-1]=1;
	
	for(i=n-2; i>=0; i--)
	{
		max=0;
		
		for(j=i+1; j<n; j++)
		{
			if(max<b[j] && a[j]>a[i])
			{
				max=b[j];
				poz=j;
			}
		}
		
		if(max==0)
			b[i]=1;
		else
			b[i]=b[poz]+1;
		
		if(maxb<b[i])
		{
			maxb=b[i];
			pozb=i;
		}
	}
	
	
	fo<<maxb<<'\n';
	
	int prec=a[pozb];
	
	fo<<a[pozb]<<" ";
	
	
	for(i=pozb+1; i<n; i++)
	{
		if(b[i]==maxb-1 && prec<a[i])
		{
			maxb--;
			
			fo<<a[i]<<" ";
		
			prec=a[i];
		}
	}
	
	fi.close();
	fo.close();
	
	return 0;
}