Cod sursa(job #2896009)

Utilizator David0911David Teregovan David0911 Data 29 aprilie 2022 18:52:27
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int v[100001], d[100001], maxi2 = 1, precedent[100001];
int n;
void pozi(int x)
{
    if(x != 0)
    {
        pozi(precedent[x]);
        fout << v[x] << " ";
    }
}
int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
    {
        fin >> v[i];
        d[i] = 1;
    }
    for(int i = 2; i <= n; i++)
    {
        int maxi = 0;
        for(int j = i - 1; j >= 1; j--)
        {
            if(d[j] > maxi && v[i] > v[j])
            {
                maxi = d[j];
                precedent[i] = j;
            }
        }
        d[i] = 1 + maxi;
    }
    int poz;
    for(int i = 1; i <= n; i++)
    {
        if(maxi2 < d[i])
        {
            maxi2 = d[i];
            poz = i;
        }
    }
    fout << maxi2 << '\n';
    pozi(poz);
    return 0;
}