Cod sursa(job #1893057)

Utilizator EzrealHorodinca Mihai Ezreal Data 25 februarie 2017 14:23:10
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f ("scmax.in");
ofstream g ("scmax.out");

int v[200], best[200], poz[200], fnl[200];
int n;

void calcul (int i)
{
    int m=0, p=0;
    for (int j=i-1; j>=0; j--)
        if (v[j] < v[i])
            if (m < best[j])
            {
                m = best[j];
                p = j;
            }
    best[i] = m+1;
    poz[i] = p;
}

int main()
{
    f >> n;
    for (int i=1; i<=n; i++)
        f >> v[i];
    for (int i=1; i<=n; i++)
        calcul (i);
    int m=0, p=0, mi=0;
    for (int i=1; i<=n; i++)
        if (m < best[i])
        {
            m = best[i];
            p = poz[i];
            mi = i;
        }
    int j = 1;
    g << m << '\n';
    fnl[0] = v[mi];
    while (p != 0)
    {
        fnl[j] = v[p];
        p = poz[p];
        j++;
    }
    for (int i=j-1; i>=0; i--)
        g << fnl[i] << ' ';
    return 0;
}