Cod sursa(job #1419528)

Utilizator ArkinyStoica Alex Arkiny Data 15 aprilie 2015 21:16:32
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include<fstream>
#include<iostream>
using namespace std;

#define MAX 100001



int V[MAX];
int B[MAX];
int P[MAX];
int st[MAX];
ifstream in("scmax.in");
ofstream out("scmax.out");


int main()
{


	int max=(1<<31);
	int pos=1,N,i,j;

	in>>N;
	
	for(i=1;i<=N;i++)
		in>>V[i];

	for(i=1;i<=N;i++)
	{

		for(j=1;j<=i;j++)

			if(V[i]>V[i-j] && B[i]<B[i-j])
			{
			    B[i]=B[i-j];
				P[i]=i-j;
			}
		++B[i];
		if(B[i]>max)
			max=B[i],pos=i;
	}
	out<<B[pos]<<'\n';
	int nst=1,l;
	l=B[pos];
	st[1]=V[pos];
	for(i=2;i<=l;i++)
	{
		pos=P[pos];
		st[i]=V[pos];

	}
	for(i=l;i>=1;i--)
		out<<st[i]<<" ";
	return 0;
}