Cod sursa(job #2881666)

Utilizator NFJJuniorIancu Ivasciuc NFJJunior Data 30 martie 2022 18:34:14
Problema Subsir crescator maximal Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.66 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
#define cin f 
#define cout g
const int Max = 1e5 + 1;

int n, arr[Max], lmax[Max], pred[Max];
int k, poz, ans[Max];
int main()
{
	cin >> n;
	for(int i=1;i<=n;i++)
	{
		cin >> arr[i];
		lmax[i] = 1;
		pred[i] = -1;
	}
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<i;j++)
			if(arr[j] < arr[i] and lmax[i] < lmax[j] + 1)
			{
				lmax[i] = lmax[j] + 1;
				pred[i] = j;
			}
	}
	cout<<lmax[n]<<'\n';
	k = lmax[n], poz = n;
	while(k > 0)
	{
		ans[k --] = arr[poz];
		poz = pred[poz];
	}
	for(int i=1;i<=lmax[n];i++)
		cout<<ans[i]<<" ";
	return 0;
}