Cod sursa(job #2113795)

Utilizator CozmaCatalinCozma Catalin CozmaCatalin Data 25 ianuarie 2018 05:43:44
Problema Subsir crescator maximal Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>
#define MAX 1005

using namespace std;

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

int Vector[MAX];
int Solutie[MAX];
int Afisare[MAX];
int Max;
int N,j,Pozitie;

void Read()
{
    in >> N;

    for ( int i = 1; i <= N ; ++i)
    {
        int x;
        in >> x;
        Vector[i] = x;
    }
}

void SCLM()
{
    Solutie[N] = 1;
    Afisare[N] = N+1;

    for  (int i = N-1; i >= 1 ; --i)
    {
        Max = 0;
        Pozitie = N+1;

        for ( j = i + 1; j <= N ; ++j)
            if(Vector[i] <= Vector[j] && Max < Solutie[j])
                          {
                             Pozitie = j;
                              Max = Solutie[j];
                          }

        Solutie[i] = Max + 1;
        Afisare[i] = Pozitie;
    }
    Pozitie = 1;

    for ( int i =1; i <= N ; ++i)
    {
        if(Solutie[Pozitie] < Solutie[i]) Pozitie=i;
    }

    out << Solutie[Pozitie] <<'\n';

    while(Pozitie  != N+1)
    {
        out << Pozitie<<" ";
        Pozitie = Afisare[Pozitie];
    }


}

int main()
{
    Read();
    SCLM();

    return 0;

}