Cod sursa(job #2610951)

Utilizator andreihaivas006Daniel Haivas andreihaivas006 Data 5 mai 2020 22:13:45
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>
#define nmax 100005
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
///Varianta o(n^2)
int n, a[nmax], lis[nmax], sol[nmax], nsol;
void Citire()
{
    int i;
    fin >> n;
    for (i = 1; i <= n; i++)
        fin >> a[i];
}
void Rezolvare()
{
    int i, j, mx;
    lis[1] = 1;
    for (i = 2; i <= n; i++)
    {
        mx = 0;
        for (j = 1; j < i; j++)
            if (a[j] < a[i] && mx < lis[j])
                mx = lis[j];
        lis[i] = 1 + mx;
    }
    mx = 0;
    for (i = 1; i <= n; i++)
        mx = max(mx, lis[i]);
    fout << mx << "\n";
    for (i = n; i >= 1; i--)
        if (lis[i] == mx)
        {
            sol[++nsol] = a[i];
            mx--;
        }
    for (i = nsol; i >= 1; i--)
        fout << sol[i] << " ";
}
int main()
{
    Citire();
    Rezolvare();
    return 0;
}