Cod sursa(job #1971172)

Utilizator SolcanMihaiSolcan Mihai Andrei SolcanMihai Data 19 aprilie 2017 21:47:01
Problema Subsir crescator maximal Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <cstdio>
#include <vector>

using namespace std;

const int N = 100005;

int n;
int sir[N];

int valori[N];
int poz[N];

int main()
{
	freopen("scmax.in", "r", stdin);
	freopen("scmax.out", "w", stdout);

	scanf("%d", &n);
	int nrMax = -1;

	for(int i = 0; i < n; i++)
	{
		scanf("%d", &sir[i]);

		for(int j = 0; j <= i; j++)
		{
			if(valori[j] == 0 || valori[j] >= sir[i])
			{
				valori[j] = sir[i];
				poz[i] = j;

				if(nrMax < j)
				{
					nrMax = j;
				}

				break;
			}
		}
	}

	vector<int> sol;
	int nr = nrMax;

	for(int i = n - 1; i >= 0; i--)
	{
		if(poz[i] == nr)
		{
			nr--;
			sol.push_back(sir[i]);
		}
	}

	printf("%d\n", sol.size());

	for(int i = sol.size() - 1; i >= 0; i--)
	{
		printf("%d ", sol[i]);
	}

	printf("\n");

	return 0;
}