Cod sursa(job #1108880)

Utilizator acelasiStanciu Rares acelasi Data 16 februarie 2014 14:41:10
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>
using namespace std;

/**
 * Initializare
 */
int v[20], l[20], n, i, k, maxim, t;


int main()
{
    /**
     * Citirea elementelor
     */
    ifstream f("scmax.in");
    f >> n;
    for (i = 1; i <= n; i++)
    {
        f >> v[i];
    }
    f.close();

    /**
     * Aflarea sirului maximal prin metoda programarii dinamice
     */
    l[n] = 1;
    for (k = n-1; k >= 1; k--)
    {
        maxim = 0;
        for (i = k + 1; i <= n; i++)
            if (v[i] >= v[k] && l[i] > maxim)
                maxim = l[i];
        l[k] = 1 + maxim;
    }

    maxim = l[1];
    t = 1;
    for (k = 1; k <= n; k++)
    {
        if (l[k] > maxim)
        {
            maxim = l[k];
            t = k;
        }
    }

    /**
     * Afisarea solutiei
     */
     g << l[t] << '\n';
     g << v[t] << " ";
     for (i = t + 1; i <= n; i++)
        if (v[i] >= v[t] && l[i] == maxim - 1)
        {
            g << v[i] << " ";
            maxim--;
        }

    g.close();
    return 0;
}