Cod sursa(job #2462447)

Utilizator pslaPislariu Alexandru psla Data 27 septembrie 2019 12:52:22
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#define Nmax 100000
using namespace std;

void citire(int &n, int x[])
{ifstream in("scmax.in");

    in>>n;
    for(int i=0; i<n; i++)
        in>>x[i];

in.close();
}

void subsir_crescator(int n, int x[],int &lS, int s[])
{/*Functia determina cel mai lung subsir crescator al sirului x*/
    int L[Nmax];/*L[i] = lungimea unui subsir maxim cu capatul in i */
    int lM=0,pM=0;/*lungimea subsirului si pozitia capatului*/
    int capat=0;/*valoarea ultimului element din subsir*/

    for(int i=0; i<n; i++)
    {
        L[i] = 0;

        for(int j=0; j<i; j++)
            if(x[j]<x[i] and L[j]>L[i])
                L[i] = L[j];
        L[i]+=1;/*adaugam si capatul*/

        if(L[i]>lM)
        {
            lM = L[i];
            pM = i;
            capat = x[i];
        }

    }

/*Construim subsirul*/
    s[lS] = capat; lS=1;

    for(int i=pM-1; i>=0; i--)
        if(x[i]<capat and L[i]==lM-1)
        {
            s[lS] = x[i]; lS++;

            capat = x[i]; lM--;
        }

}

void afisare(int lS, int s[])
{ofstream out("scmax.out");
    out<<lS<<'\n';

    for(int i=lS-1; i>=0; i--)
        out<<s[i]<<" ";

out.close();
}

int main()
{
    int n, x[Nmax];
    citire(n,x);

    int lS=0, s[Nmax];/*subsirul crescator*/
    subsir_crescator(n,x,lS,s);

    afisare(lS,s);
    return 0;
}