Cod sursa(job #3220533)

Utilizator CraiuAndreiCraiu Andrei David CraiuAndrei Data 3 aprilie 2024 22:58:56
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");

int n, a[100005], lis[100005], poz[100005], p, m;

int main()
{
	int i,j ;
	fin >> n;
	for (i = 1; i <= n; i++)
		fin >> a[i];
	lis[n] = 1;
	poz[n] = -1;
	m = 1;
	p = n;
	for (i = n - 1; i >=1; i--)
	{
		//lungimea maxima a sirului care se incepe la i
		lis[i] = 1;
		poz[i] = -1;	
		for(j=i+1;j<=n;j++)
			if (a[i] < a[j] && lis[i] < lis[j] + 1)
			{
				lis[i] = lis[j] + 1;
				poz[i] = j;
				if (lis[i] > m)
				{
					m = lis[i];
					p = i;
				}
			}
	}
	fout << m << "\n";
	while (p != -1)
	{
		fout << a[p] << " ";
		p = poz[p];
	}
	return 0;
	return 0;
}