Cod sursa(job #2090608)

Utilizator Teodor.mTeodor Marchitan Teodor.m Data 18 decembrie 2017 15:37:20
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMax = 1e5 + 50;
int a[NMax], DP[NMax], poz[NMax];

int main()
{
	int n;
	fin >> n;

	for(int i = 1; i <= n; ++i)
		fin >> a[i];

	int maxim = 1;
	int start = n;
	DP[n] = 1;
	poz[n] = -1;
	for(int i = n - 1; i >= 1; --i) {
		DP[i] = 1;
		poz[i] = -1;

		for(int j = i + 1; j <= n; ++j) {
			if(a[i] < a[j] && DP[i] < DP[j] + 1) {
				DP[i] = DP[j] + 1;
				poz[i] = j;

				if(DP[i] > maxim) {
					maxim = DP[i];
					start = i;
				}
			}
		}
	}


	fout << maxim << '\n';
	while(start != -1) {
		fout << a[start] << " ";
		start = poz[start];
	}
	return 0;
}