Pagini recente » Cod sursa (job #219234) | Cod sursa (job #2538500) | Cod sursa (job #829458) | Cod sursa (job #449159) | Cod sursa (job #2244965)
#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;
}