[Sfaturi] Submatricea de arie maximala

[•scipianus]

Am de facut o problema cu o matrice de 0 si 1,in care trebuie sa aflu submatricea de arie maximala compusa numai din elemente 0.Practic problema se reduce la o alta astfel : intr-o alta matrice pe pozitia (i,j) voi avea numarul de elemente 0 consecutive de deasupra sa inclusiv el insusi(asta in cazul in care pe pozitia (i,j) am un element 0) si apoi se face o parcurgere pe fiecare linie a matricei noi rezolvand la fiecare linie urmatoarea problema auxiliara (cea la care vreau sa primesc niste indicatii despre cum s-ar rezolva LINIAR) :

Problema auxiliara:
Se considera un sir de n numere naturale ce reprezinta inaltimea unor turnuri pozitionate unul dupa altul,lipite,in aceasta ordine.Sa se determine care este dreptunghiul de arie maxima(sau mai bine spus care este acea arie maxima ; la fel si la problema cu submatricea trebuie sa aflu doar aria maxima, nu neaparat si locatia sa).

Explicatie(problema principala-crearea celei de-a 2-a matrici):
Daca am matricea:                       Atunci a 2-a matrice va arata astfel:

1 0 1 0 1                                0 1 0 1 0
0 0 1 0 0                                1 2 0 2 1
1 1 0 1 1                                0 0 1 0 0
1 0 0 1 0                                0 1 2 0 1
0 0 0 0 1                                1 2 3 1 0

Explicatie(problema auxiliara):
Daca avem sirul 2 4 2 1 5 4 1  atunci reprezentarea ar fi urmatoarea :


Asa cum am precizat,doresc doar indicatii spre a gasi solutia liniara la problema auxiliara  

[•pauldb]

S-a mai discutat pe aceasta tema la problema Bmatrix. Ar trebui sa te ajute indicatiile de acolo.

[•scipianus]

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-source

Mentin 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).  

[•devilkind]

Ideea e ca pentru fiecare numarul din vectorul vrei sa afli primul numar din stanga si din dreapta lui care sunt mai mici de cat el (practic vrei sa construiesti un dreptunghi cu inaltimea egala cu elementul de pe pozitia si vrei sa vezi cat de mult il extinzi). Acuma pentru a afla pentru fiecare numar primul element din stanga mai mic el, bagi pe rand elementele intr-o stiva sortata crescator. Ideea e ca atunci cand adaugi un element in stiva, scoti din varful stivei elementele mai mari decat el. Dupa ce ai scos toate acele elemente, elementul din varful stivei e fix primul numar din stanga lui mai mic decat el. Faci fix la fel ca sa gasesti primul element din dreapta mai mic decat el.

[•scipianus]

Gata,am reusit sa inteleg metoda si sa fac problema.Am avut o dilema la postul urmator in care credeam ca "-" dintre pozitia curenta si pozitia in care a fost.... era o explicatie,nu semnul minus si ma intrebam de ce e varful stivei * pozitia curenta 

Initial calculezi A[i,j] = numarul de 0 consecutivi deasupra pozitiei i, j. Apoi parcurgi linie cu linie matricea si iti propui sa afli cel mai mare dreptunghi plin cu 0 deasupra liniei i (linia curenta). Parcurgi linia de la stanga la dreapta si adaugi valorile A[i,j] intr-o stiva. Cat timp elementul din stiva este mai mare decat elementul curent acesta este scos. Vezi daca varful stivei * (pozitia curenta - pozitia in care a fost varful adaugat in stiva) este mai bun ca solutia si actualizezi. Reiei apoi acelasi algoritm pe linie de la dreapta la stanga si in final vei obtine cel mai bun dreptunghi deasupra liniei i. De mentionat ca cu acest algoritm, nu poti (cel putin nu stiu eu cum) afla cel mai mare dreptunghi cu 0 cu coltul in (i, j).

Ma gandesc dreptunghiul si patratul maxim de 0 sunt dinamici care ar trebui adaugate in arhiva educationala pe viitor. Buru, modifici tu pagina?

Abia dupa m-am gandit ca ala e minus,am luat pas cu pas pe exemplu si am inteles  Mersi de ajutor