Cod sursa(job #778440)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 14 august 2012 19:39:04
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb

#include <fstream>

inline unsigned int ascending (unsigned int *numbers, unsigned int *length, unsigned int n)
{
	unsigned int i(n - 1), j, new_length, max_length(1), first(0);
	while (true)
	{
		length[i] = 1;
		for (j = i + 1 ; j <= n ; ++j)
		{
			if (numbers[i] < numbers[j])
			{
				new_length = length[j] + 1;
				if (new_length > length[i])
					length[i] = new_length;
			}
		}
		if (length[i] > max_length)
		{
			max_length = length[i];
			first = i;
		}
		if (i)
			--i;
		else
			break;
	}
	return first;
}

int main (void)
{
	unsigned int n;
	std::ifstream input("scmax.in");
	input >> n;
	unsigned int *numbers(new unsigned int [n]);
	for (unsigned int *iterator(numbers), *end(numbers + n) ; iterator < end ; ++iterator)
		input >> *iterator;
	input.close();
	unsigned int *length(new unsigned int [n]( ));
	--n;
	length[n] = 1;
	unsigned int first(ascending(numbers,length,n)), max_length(length[first]);
	std::ofstream output("scmax.out");
	output << max_length << '\n';
	unsigned int last_number;
	while (true)
	{
		output << numbers[first];
		--max_length;
		last_number = first;
		if (max_length)
		{
			output.put(' ');
			while (length[first] != max_length || numbers[first] < numbers[last_number])
				++first;
		}
		else
			break;
	}
	output.put('\n');
	output.close();
	delete [ ] numbers;
	delete [ ] length;
	return 0;
}