Cod sursa(job #636611)

Utilizator VisuianMihaiMihai Visuian VisuianMihai Data 19 noiembrie 2011 21:46:50
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include<fstream>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int maxim[100001], poz[100001];
long int a[100001];
int main()
{
	int n, i, j, max = 0, p;
	fin >> n;
	for ( i = 1; i <= n; i++ )
		fin >> a[i];
	maxim[n] = 1;
	for ( i = n-1; i >= 1; i-- )
	{
		maxim[i] = 1;
		for ( j = i+1; j <= n; j++ )
			if ( a[i] < a[j] && maxim[i] <= maxim[j] )
			{
				maxim[i] = maxim[j] + 1;
				poz[i] = j;
			}
			if ( maxim[i] > max )
			{
				max = maxim[i];
				p = i;
			}
	}
	fout << max << '\n';
	i = p;
	while ( i != poz[n] )
	{
		fout << a[i] << ' ';
		i = poz[i];
	}
	fin.close();
	fout.close();
	return 0;
}