Cod sursa(job #1175948)

Utilizator vlasinalinVlasin Alin vlasinalin Data 25 aprilie 2014 10:50:36
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <stdio.h>
#include <iostream>
#include <fstream>
using namespace std;

#define in "scmax.in"
#define out "scmax.out"
#define MAXN 100001

int n, arr[MAXN], best[MAXN], parent[MAXN], maxi;

void read_input()
{
	ifstream fin(in);
	if (fin.is_open())
	{
		fin >> n;
		for (int i = 1; i <= n; ++i)
		{
			fin >> arr[i];
			//cout << arr[i] << ' ';
		}
		fin.close();
	}
}

int get_parent_index(int ci)
{
	int pi = 0;
	int cval = arr[ci];
	int max = 0;
	for (int i = 1; i < ci; ++i)
	{
		if (arr[i] > max && arr[i] < cval)
		{
			max = arr[i];
			pi = i;
		}
	}
	return pi;
}

void resolve()
{
	int pi;
	for (int i = 1; i <= n; ++i)
	{
		pi = get_parent_index(i);
		parent[i] = pi;
		best[i] = best[pi] + 1;
		if (best[i] > best[maxi])
		{
			maxi = i;
		}
	}
}

void print_debug()
{
	cout << '\n';
	for (int i = 1; i <= n; ++i)
	{
		cout << best[i] << ' ';
	}
}

void print_solution()
{
	ofstream fout(out);
	int sol[MAXN];
	int max_len = best[maxi];
	int k = max_len;
	while (maxi > 0)
	{
		sol[--k] = arr[maxi];
		maxi = parent[maxi];
	}

	fout << max_len << '\n';
	for (int i = 0; i < max_len; ++i)
	{
		fout << sol[i] << ' ';
	}
}

int main()
{
	read_input();

	resolve();

	//print_debug();

	print_solution();

	//char x;
	//cin >> x;

	return 0;
}