Cod sursa(job #1781824)

Utilizator LazarAndreiLazar Andrei Teodor LazarAndrei Data 17 octombrie 2016 15:07:46
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>
using namespace std;

ifstream in ("sxmax.in");
ofstream out ("scmax.out")
int L[1000] , arr[1000] , 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;
        Max = 0;

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

        }
        L[i] = 1 + Max;

        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;
}