Cod sursa(job #2022098)

Utilizator anderut22Sandu Andrei anderut22 Data 15 septembrie 2017 17:28:31
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#define VMAX 100001
using namespace std;
ifstream cin("scmax.in");
ofstream cout("scmax.out");

void citire();
void rulare(int k);
void afisare();

int v[VMAX], lgmax[VMAX], urm[VMAX], n, Llis, lis;

int main()
{
    citire();
    rulare(n-1);
    afisare();
    return 0;
}

void citire()
{
	int i;
	cin >> n;
	for (i=1; i<=n; i++) cin >> v[i];
	lgmax[n]=1;
}

void rulare(int k)
{
	int i;
	if (!k) return;
		else
		{
			for (i=k+1; i<=n; i++) if ((v[k]<v[i])&&(lgmax[k]<=lgmax[i]+1))
			{
				urm[k]=i;
				lgmax[k]=1+lgmax[i];
				if (lgmax[k]>=Llis)
				{
					Llis=lgmax[k];
					lis=k;
				}
			}
			rulare(k-1);
		}
}

void afisare()
{
	int i;
	cout << Llis<< '\n';
	for (i=lis; urm[i]; i=urm[i]) cout << v[i]<< ' ';
	cout << v[i];
}