Cod sursa(job #1781842)

Utilizator LazarAndreiLazar Andrei Teodor LazarAndrei Data 17 octombrie 2016 15:18:09
Problema Subsir crescator maximal Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in ("scmax.in");
ofstream out ("scmax.out");
int L[100001] , arr[100001] , p ,  Max , best , N;

void read ()
{
    in >> N ;
    for(int i = 1 ; i <= N ; ++ i)
        in >> arr[i];
}

void dinamica ()
{
    L[N] = 1;

    for(int i = N - 1 ; i >= 1 ; -- i)
    {
        L[i] = 1;

        for(int j = i + 1 ; j <= N ; ++ j)
        {
            if(arr[i] < arr[j] && L[i] < L[j] + 1)
            {
                L[i] = L[j] + 1;
            }
        }

        if(L[i] > best)
            best = L[i] , p = i;
    }
}
void print ()
{
    out << best << '\n';
    for(int i = p ; i <= N ; ++ i)
    {
        if(i != N)
        {
            if(L[i + 1] == 1)
            {
                if(arr[i] >= arr[i-1])
                    out << arr[i] << " ";
            }
            else
            {

                if(arr[i + 1] > arr[i] && L[i + 1] < L[i])
                    out << arr[i] << " ";
            }
        }
        else
        {
            if(arr[i] > arr[i-1] && L[i] < L[i-1])
                out<< arr[i] << " ";
        }
    }
}
int main()
{
    read();
    dinamica();
    print();
    return 0;
}