Pagini recente » Cod sursa (job #1840323) | Cod sursa (job #1605815) | Cod sursa (job #1230086) | Cod sursa (job #548875) | Cod sursa (job #2938021)
//
// main.cpp
// Subsir crescator maximal (infoarena)
//
// Created by Andrei Bădulescu on 11.11.22.
//
//#include <iostream>
#include <fstream>
using namespace std;
string file = "scmax";
ifstream cin(file + ".in");
ofstream cout(file + ".out");
const int N = 100000;
int results[N + 1], numbers[N + 1];
int n;
void printSolution(int maxPos, int max, int remainder) {
if (!remainder) {
return;
}
if (numbers[maxPos] <= max && remainder == results[maxPos]) {
printSolution(maxPos - 1, numbers[maxPos], remainder - 1);
cout << numbers[maxPos] << ' ';
} else {
printSolution(maxPos - 1, max, remainder);
}
}
int main() {
cin >> n;
for (auto i = 1; i <= n; i++) {
cin >> numbers[i];
}
int maxPos = 0;
for (auto i = 1; i <= n; i++) {
for (auto j = 1; j < i; j++) {
if (numbers[j] < numbers[i]) {
results[i] = max(results[i], results[j]);
}
}
results[i]++;
if (results[i] > results[maxPos]) {
maxPos = i;
}
}
cout << results[maxPos] << '\n';
printSolution(maxPos, numbers[maxPos], results[maxPos]);
return 0;
}