Cod sursa(job #1497882)

Utilizator ArkinyStoica Alex Arkiny Data 7 octombrie 2015 18:57:38
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include<fstream>
#include<iostream>
#include<string.h>
using namespace std;

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

#define MAX 100001

struct Best
{
	int v;
	int l;
}B[MAX];
int A[MAX],N;

void afis(int i)
{
	if (B[i].l)
		afis(B[i].l);
	out << A[i] << " ";
}

int main()
{
	int i, j;
	in >> N;
	for (i = 1;i <= N;++i)
		in >> A[i];
	int BEST = -1,BEST_IND=0;
	for (i = 1;i <= N;++i)
	{
		int max = 0;
		int ind = 0;
		for (j = 1;j < i;++j)
			if (A[i]>A[j] && B[j].v > max)
				max = B[j].v,ind=j;

		B[i].v = max + 1;
		B[i].l = ind;
		if (B[i].v > BEST)
			BEST = B[i].v, BEST_IND = i;
	}

	out << B[BEST_IND].v << '\n';
	afis(BEST_IND);

	return 0;
}