Pagini recente » Cod sursa (job #1370467) | Cod sursa (job #2711143) | Cod sursa (job #434392) | Cod sursa (job #1673284) | Cod sursa (job #2494315)
#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;
}