Cod sursa(job #2244965)

Utilizator DRLDRLRaul Ronald Galea DRLDRL Data 24 septembrie 2018 14:20:38
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#pragma once

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

using namespace std;

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


int sir[100], N, dpB[100], pU[100];

// 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 << sir[current] << " ";
	while (nr > 1) {
		fout << sir[pU[current]] << " ";
		current = pU[current];
		nr--;
	}
	fout << "\n";
}


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