Cod sursa(job #2505334)

Utilizator Robert.BrindeaBrindea Robert Robert.Brindea Data 6 decembrie 2019 18:41:16
Problema Subsir crescator maximal Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin ("scmax.in");
ofstream fout ("scmax.out");

int a[100005];
int s[100005];
int n, nq;

int main()
{
    fin >> n;
    for(int i = 0; i < n; i++)
        fin >> a[i];
    for(int i = 0; i < n; i++)
    {
        int mmm = 0;
        for(int j = 0; j < i; j++)
        {
            if(a[j] < a[i])
            {
                mmm = max(s[j], mmm);
            }
        }
        s[i] = mmm+1;
    }
    int mx, pos;
    mx = 0;
    for(int i = 0; i < n; i++)
    {
        if(s[i] > mx)
        {
            mx = s[i];
            pos = i;
        }
    }
    fout << mx << "\n";
    s[nq++] = a[pos];
    int cr = a[pos];
    for(int i = pos; i >= 0; i--)
    {
        if(a[i] < a[pos] && s[i] == s[pos]-1)
        {
            pos = i;
            s[nq++] = a[i];
        }
    }
    for(int i = nq-1; i >= 0; i--)
        fout << s[i] << " ";
    return 0;
}