Cod sursa(job #2244973)

Utilizator DRLDRLRaul Ronald Galea DRLDRL Data 24 septembrie 2018 14:40:43
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#pragma once

#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>

using namespace std;

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

#define dim 100001

int sir[dim], N, dpB[dim], pU[dim];
vector<int> lis;

// dp[i] = subs max care se termina in i

void bu() {
	int maxc = 0;
	dpB[1] = 1;
	for (int i = 2; i <= N; i++) {
		maxc = 0;
		for (int j = i - 1; j >= 1; j--) {
			if (sir[i] >= sir[j]) {
				if (dpB[j] > maxc) {
					maxc = dpB[j];
					dpB[i] = dpB[j] + 1;
					pU[i] = j;
				}
			}
		}
	}

}



void afis() {
	// bottom up
	int current, allMax = 0;
	for (int i = 1; i <= N; i++) {
		if (dpB[i] > allMax) {
			allMax = dpB[i];
			current = i;
		}
	}
	int nr = dpB[current];
	fout << allMax << "\n";

	lis.push_back(sir[current]);
	while (nr > 1) {
		lis.push_back(sir[pU[current]]);
		current = pU[current];
		nr--;
	}
	
	for (int i = lis.size() - 1; i >= 0; --i)
		fout << lis[i] << " ";
}


int main() {
	fin >> N;
	for (int i = 1; i <= N; i++)
		fin >> sir[i];
	bu();
	afis();
	return 0;
}