Cod sursa(job #1179567)

Utilizator stef93Stefan Gilca stef93 Data 28 aprilie 2014 21:26:08
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <iostream>
#include <climits>

using namespace std;

int sol[100000], urm[100000], a[100000];

int main()
{
	ifstream in("scmax.in");
	ofstream out("scmax.out");

	int n, i, j , max = INT_MIN  ,ind;
	

	in >> n;

	for (i = 0; i < n; i++)
	{
		in >> a[i];
	}

	for (i = 0; i < n; i++)
	{
		sol[i] = 1;
		urm[i] = -1;
	}

	for (i = n - 2; i >= 0; i--)
	{
		for (j = i + 1; j < n ; j++)
		{
			if (a[j] > a[i] && sol[j] + 1 > sol[i])
			{
				sol[i] = sol[j] + 1;
				urm[i] = j;
				if (sol[i] > max)
				{
					max = sol[i];
					ind = i;
				}
			}
		}
	}

	out << max << '\n';
	
	while (ind != -1)
	{
		out << a[ind] << ' ' ;
		ind = urm[ind];
	}

	out << '\n';
	in.close();
	out.close();
	return 0;
}