Cod sursa(job #2628190)

Utilizator flashraneSzasz Csongor flashrane Data 14 iunie 2020 20:41:33
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.81 kb
#include <iostream>
#include <fstream>
using namespace std;

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

int h[100001], e[100001], n, i, j, maxi;
long int a[100001], ans[100001];

int main()
{
    fin >> n;
    for (i = 0; i < n; i++)
    {
        fin >> a[i];
        e[i] = -1;
    }
    h[0] = 1;
    for (i = 1; i < n; i++)
    {
        maxi = i;
        for (j = i-1; j >= 0; j--)
        {
            if (a[j] < a[i] && h[j] > h[maxi])
                maxi = e[i] = j;
        }
        if (e[i] != -1)
            h[i] = h[maxi]+1;
        else
            h[i] = 1;
    }
    int max_h = 0;
    for (i = 1; i < n; i++)
    {
        if (h[i] > h[max_h])
            max_h = i;
    }
    for (i = h[max_h]-1, j = max_h; i >= 0; i--)
    {
        ans[i] = a[j];
        j = e[j];
    }

    fout << h[max_h] << "\n";
    for (i = 0; i < h[max_h]; i++)
        fout << ans[i] << " ";
    /*
    for (i = 0; i < n; i++)
        fout << a[i] << " ";
    fout << "\n";
    for (i = 0; i < n; i++)
        fout << h[i] << " ";
    fout << "\n";
    for (i = 0; i < n; i++)
        fout << e[i] << " ";
    */
}

// n    11
// a    24  12  15  9   20  19  6   32  21  23  16
// i    0   1   2   3   4   5   6   7   8   9   10

// h    1   1   2   1   3   3   1   4   4   5   3
// e    -1  -1  1   -1  2   2   -1  5   5   8   2

/* pseudo solution
main()
{
    for 1 to n
    {
        for i-1 to 0
        {
            //find number with the highest length which is at the same time smaller than a[i]
            if found a number
            {
                maxi = j;
                e[i] = maxi;
            }
        }
        if (e[i] != -1)
            h[i] = h[maxi]+1;
    }
    find the max val of h[]
    print the wanted elements
}
*/