Cod sursa(job #1464674)

Utilizator tudorgalatanRoman Tudor tudorgalatan Data 24 iulie 2015 10:57:56
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>

using namespace std;

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

int v[100000], l[100000];
int n, i, k, t, maxim;

int main ()
{
    f >> n;
    for (i=1; i<=n; i++)
        f >> v[i];
    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;
        }
    g << maxim << "\n" << v[t] << " ";
    for (i=t+1; i<=n; i++)
        if (v[i]>v[t] && l[i]==maxim-1)
        {
            g << v[i] << " ";
            maxim--;
        }
    return 0;
}