Cod sursa(job #2927922)

Utilizator tiut_cristianTiut Cristian tiut_cristian Data 21 octombrie 2022 20:19:50
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
//#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

int main() //------------------------- DE FACUT AFISAREA ELEM DIN SUBSIR
{
    ifstream cin("scmax.in");
    ofstream cout("scmax.out");

    int n;
    cin >> n;

    vector<int> a(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];

    vector<int> best(n);
    vector<int> prev(n, -1);
    int best_max = 0;
    int best_index = -1;
    for(int i = 0; i < n; i++)
    {
        int maxim = 0;
        for(int j = 0; j < i; j++)
            if(a[j] < a[i])
                if(best[j] > maxim)
                {
                    maxim = best[j];
                    prev[i] = j;
                }
        best[i] = 1 + maxim;
        if(best[i] > best_max)
        {
            best_max = best[i];
            best_index = i;
        }
    }

    cout << best_max << '\n';
    stack<int> st;
    while(best_index != -1)
    {
        st.push(best_index);
        best_index = prev[best_index];
    }
    while(!st.empty())
    {
        cout << a[st.top()] << ' ';
        st.pop();
    }

    return 0;
}