Cod sursa(job #3032189)

Utilizator Cristi3956Pop Cristian Cristi3956 Data 21 martie 2023 17:45:54
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <bits/stdc++.h>
#define MAX 100001
using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n, i, j, maxim, lmax, nr, s[MAX], v[MAX], p, a[MAX];

int main()
{
    fin >> n;
    for (i = 1; i <= n; i++)
        fin >> a[i];
    v[n] = 1;
    for (i = n - 1; i >= 1; i--)  {
        maxim = 0;
        for (j = i + 1; j <= n; j++)
            if (a[j] > a[i] and v[j] > maxim)
                maxim = v[j], p = j;
        v[i] = 1 + maxim;
        s[i] = p;
        if (v[i] > lmax)
            lmax = v[i], nr = i;        
    }
    fout << lmax << '\n';
    for (i = 1; i <= lmax; i++) {
        fout << a[nr] << ' ';
        nr = s[nr];
    }
    return 0;
}