Cod sursa(job #986565)

Utilizator Anca_PaneaPanea Anca Anca_Panea Data 19 august 2013 02:57:47
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
using namespace std;
#include<fstream>
#define Nmax 100005
ifstream eu("scmax.in");
ofstream tu("scmax.out");
int N,A[Nmax],best[Nmax],poz[Nmax],PozMa,maxim;
void read()
{
	eu>>N;
	for(int i=1;i<=N;i++)
		eu>>A[i];
}
void solve()
{
		for(int i=N;i>=1;i--)
		{
			best[i]=0;
			for(int j=i+1;j<=N;j++)
				if(A[i]<A[j]&&best[i]<best[j])
				{
					best[i]=best[j];
					poz[i]=j;
				}
			best[i]++;
		}
	for(int i=1;i<=N;i++)
		if(best[i]>maxim)
		{
			maxim=best[i];	
			PozMa=i;
		}
}
int main()
{
	read();
	solve();
	int i;
	tu<<maxim<<"\n";
	i=PozMa;
	while(i)
	{
		tu<<A[i]<<" ";
		i=poz[i];
	}
	return 0;
}