Pagini recente » Cod sursa (job #219185) | Cod sursa (job #440741) | Cod sursa (job #3152901) | Cod sursa (job #2590452) | Cod sursa (job #2244973)
#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;
}