Cod sursa(job #2571072)

Utilizator Robys01Robert Sorete Robys01 Data 4 martie 2020 20:57:43
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <bits/stdc++.h>
#define NMAX 100001
using namespace std;

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

int n, v[NMAX], L[NMAX];

int main()
{
    fin>>n;
    for(int i=1; i<=n; i++)
        fin>>v[i];

    L[n] = 1;

    int t, max_t = 0;

    for(int i = n - 1; i >= 1; i--)
    {
        int maxim = 0;
        for(int j = i + 1; j<=n; j++)
            if(v[i] < v[j] && maxim < L[j])
            {
                maxim = L[j];

            }
        L[i] = maxim + 1;
        if(max_t < maxim + 1)
                {
                    t = i;
                    max_t = maxim + 1;
                }
    }

    fout<<L[t]<<'\n';
    for(int i = t; i<=n; i++)
        if(L[i] == max_t)
        {
            fout<<v[i]<<' ';
            max_t--;
        }

    return 0;
}