Cod sursa(job #1010653)

Utilizator PsychoAlexAlexandru Buicescu PsychoAlex Data 15 octombrie 2013 13:14:36
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>

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

long n, a[100001], l[100001];

void citire()
{
    fin>>n;
    for(int i = 0; i < n; i++)
    {
        fin>>a[i];
        l[i] = 1;
    }
}

void rezolvare()
{
    long maximAbs = 0, ind = 0;
    for(int i = n - 2; i >= 0; i--)
    {
        long maxim = 0;
        for(int j = i + 1; j < n; j++)
        {
            if(a[i] < a[j])
            {
                if(maxim < l[j])
                {
                    maxim = l[j];
                }
            }
        }
        l[i] = maxim + 1;
        if(l[i] > maximAbs)
        {
            maximAbs = l[i];
            ind = i;
        }
    }
    fout<<maximAbs;
    long lastNR = a[ind];
    for(int i = ind; i < n; i++)
    {
        if(l[i] == maximAbs && a[i] >= lastNR)
        {
            fout<<a[i]<<' ';
            maximAbs--;
            lastNR = a[i];
        }
//        std::cout<<l[i]<<' ';
    }
}

int main()
{
    citire();
    rezolvare();
    return 0;
}