Diagonala
O primă observaţie este aceea că dacă mutăm secvenţa de 1 de pe linia i cu i poziţii mai la stânga respectiv mai la dreapta, problema se reduce la aflarea celei mai lungi secvenţe verticale continue de 1.
Pentru a determina o astfel de secvenţă vom menţine două deque-uri, unul sortat descrescător pentru marginile din dreapta, iar celălalt crescător pentru marginile din stânga. În momentul în care introducem un nou interval, vom avea grijă să menţinem proprietăţile celor două deque-uri. Acum, există posibilitatea ca cel mai mare element din deque-ul pentru marginile din stânga să fie mai mare decât cel mai mic din deque-ul pentru marginile din dreapta, caz în care vom scoate pe rând elementele din cele două deque-uri până când cea mai mare margine din dreapta este mai mică sau egală cu cea mai mică margine din stânga. Astfel putem determina lungime maximă a unei coloane continue de 1 ce se termină pe linia actuală.
