Cod sursa(job #2216555)

Utilizator Silviu.Stancioiu@gmail.comSilviu Stancioiu [email protected] Data 27 iunie 2018 11:52:56
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <fstream>

#define MAX_N 100005

using namespace std;

int n;
int values[MAX_N] = { 0 };
int best[MAX_N] = { 0 };
int indices[MAX_N] = { 0 };

int maxPos = 0;

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

void Write(int ix)
{
	if (ix != 0)
	{
		Write(indices[ix]);
		fout << values[ix] << " ";
	}
}

int main(void)
{
	fin >> n;

	for (int i = 1; i <= n; i++)
	{
		fin >> values[i];
		
		for (int j = 1; j < i; j++)
		{
			int sum = best[j] + 1;

			if (sum > best[i] && values[j] < values[i])
			{
				best[i] = sum;
				indices[i] = j;

				if (best[i] > best[maxPos])
				{
					maxPos = i;
				}
			}
		}
	}

	fout << best[maxPos] + 1 << endl;

	Write(maxPos);

	fin.close();
	fout.close();

	return 0;
}