Cod sursa(job #1419507)

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

#define MAX 100001



int V[MAX];
int B[MAX];
int P[MAX];


ifstream in("scmax.in");
ofstream out("scmax.out");

void print(int i)
{
	if(P[i]!=0)
	{
		print(P[i]);
		out<<V[i]<<" ";
	}
	else if(P[i]==0)
		out<<V[i]<<" ";
}

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';
	print(pos);

	return 0;
}