Cod sursa(job #2494315)

Utilizator david16Leahu David david16 Data 17 noiembrie 2019 17:56:45
Problema Subsir crescator maximal Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.04 kb
#include <iostream>
#include <fstream>
using namespace std;

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

long n, maxim; //initializam variabila n, care memoreaza numarul de numere si maxim care memoreaza lungimea maxima a unui subsir crescator
struct
{
    long numar, lungime;
}sir[100000]; //definim un articol cu doua campuri, numar - care memoreaza numarul citit si lungime - care memoreaza lungimea subsirului din care face parte numarul si initializam un tablou sir, care va memora numerele

long sirmax[100000]; //initializam sirmax, care va memora sirul crescator de lungime maxima

void cauta (int n)
{
    long lgMax=0; //initializam lgMax care va memora lungimea celui mai mare subsir din dreapta numarului citit cu ultima valoare mai mica decat numarul citit
    long k=0; //initializam k care va contoriza sirmax
    for (long i=0; i<n; i++) //parcurgem toate valorile din stanga numarului
    
            if (sir[n].numar>sir[i].numar && sir[i].lungime>lgMax) //verificam daca numarul citit este mai mare decat numarul anterior si daca are cel mai lung subsir
                lgMax = sir[i].lungime, sirmax[k]=sir[i].numar, k++; //ii memoram lungimea subsirului si il memoram in sirmax
        
        sirmax[k]=sir[n].numar; //memoram si numarul citit in sirmax
        
        sir[n].lungime=lgMax+1; //memoram lungimea subsirului din care face parte numarul citit, aceasta este cu 1 mai mare decat lungimea subsirului la care va face parte
}

int main()
{
    fin >> n; //citim n
    for (long i=0; i<n; i++) //facem n operatii
    {
        fin >> sir[i].numar; //citim urmatorul numar din sir

        cauta(i); //cautam cel mai mare numar anterior cu lungimea sirului cea mai mare
        
        if (sir[i].lungime > maxim) //memoram lungimea maxima a subsirului
            maxim = sir[i].lungime;
    }
    
    fout << maxim << endl; //afisam lungimea subsirului maxim
    
    for (long i=0; i<maxim; i++) //afisam sirmax, subsirul maxim crescator
        fout << sirmax[i] << ' ';
    
    return 0;
}