Cod sursa(job #2938021)

Utilizator AndreiBadAndrei Badulescu AndreiBad Data 11 noiembrie 2022 15:39:30
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
//
//  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;
}