S-a mai discutat pe aceasta tema la problema
Bmatrix. Ar trebui sa te ajute indicatiile de acolo.
Ok.Am citit acum din acel post,insa nu prea am inteles asa de bine ideea propusa de tine si m-am chinuit sa vad pas cu pas solutia urmatoare(ultima postata) insa nu prea inteleg :
Fac exact asa cum ai explicat tu. Uite o sursa:
http://infoarena.ro/job_detail/312811?action=view-sourceMentin o stiva de perechi (inaltime, pozitie), sortate strict crescator dupa inaltime, care reprezinta candidatii pentru capatul din stanga al dreptunghiului de arie maxima. Pentru pasul i sa spunem ca ai inaltimea h. Vrei sa introduci in stiva. Daca h este mai mare decat varful stivei adaugi perechea (h, i). Altfel, scoti din stiva cat timp inaltimea din varf este mai mare strict decat h. Daca ramai in varf cu o inaltime egala cu h, nu faci nimic. Altfel adaugi perechea (h, j), unde j reprezinta ultima pozitie pe care ai sters-o din varful stivei. Stiva ar functiona astfel pe exemplul dat de tine:
Pasul 1: (4, 1).
Pasul 2: Scoti (4, 1), adaugi (3, 1). Stiva arata astfel: (3, 1).
Pasul 3: Scoti (3, 1), adaugi (2, 1). Stiva arata astfel: (2, 1).
Pasul 4: Adaugi (3, 4). Stiva arata astfel: (2, 1), (3, 4).
Pasul 5: Adaugi (4, 5). Stiva arata astfel: (2, 1), (3, 4), (4, 5).
Verficarile le fac atunci cand scot din stiva. La sfarsit am grija sa golesc de tot stiva, facand verificarile necesare.
As dori daca se poate sa-mi explici mai clar decat a spus-o aici
wefgef,eventual sa-mi arati stiva pas cu pas pentru exemplul meu din desen si verificarile necesare cand se fac(fiindca nu vad cand s-ar verifica dreptunghiul de inaltime 2 dintre pozitiile 1-3 sau dreptunghiul de inaltime 1 de pe toata linia,adica bine,nu sunt astea solutia si nu analizez orice dreptunghi,insa nu vad logica cu care ajung la candidatul pentru solutie).