Cod sursa(job #2823485)

Utilizator AdrianDiaconitaAdrian Diaconita AdrianDiaconita Data 28 decembrie 2021 17:40:08
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <bits/stdc++.h>
using namespace std;

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

const int NMAX = 100003;

int best[NMAX], a[NMAX], maxi, sol = 0, poz[NMAX], p;
int n;

void read()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
    {
        fin >> a[i];
    }
}

void dp()
{
    int i,j;
    best[n] = 1;
    poz[n] = -1;
    maxi = 1;
    p = n;
    for (i = n; i >= 1; --i)
    {
        best[i] = 1;
        poz[i]=-1;
        for (j = i+1; j <= n; ++j)
        {
            if (a[i]<a[j] && best[i]<best[j]+1)
            {
                best[i] = best[j] + 1;
                poz[i] = j;
                if (best[i] > maxi)
                {
                    maxi = best[i];
                    p = i;
                }
            }
        }
    }
}

void constr()
{
    int i;
    i = p;
    while (i != -1)
    {
        fout << a[i] << ' ';
        i = poz[i];
    }
}

int main()
{
    read();
    dp();
    fout << maxi << '\n';
    constr();               
    return 0;               
}