Trước hết, ta nhận xét là tọa độ của đỉnh tấm lưới sẽ trùng với tọa độ của các con cá.

Ta duyệt các cặp tọa độ ~X~ có thể của hai đỉnh tấm lưới (các cặp ~(i_1,i_2)~ với ~i_1 ≤ i_2~). Khi đó, ta cần chọn một cặp tọa độ ~Y~ cho hai đỉnh của tấm lưới. Nếu ta chọn cặp ~(l,j_2)~ với ~j_1 ≤ j_2~ thì lợi nhuận là:

$$P=\sum_{\substack{j_1≤j≤j_2}}\sum_{\substack{i_1≤i≤i_2}} A_{i,j}-(X_{i_2} - X_{i_1}) ∗ (Y_{j_2} - Y_{j_1})$$

Gọi:

• ~D_{i,j} =\sum_{\substack{1≤k≤i}}A_{k,j}~ (tổng các giá trị từ dòng 1 đến dòng ~i~ tại cột ~j~ của bảng ~A~)
• ~F_j = \sum_{\substack{1≤k≤j}}D_{i_2,j} - D_{i_1−1,j}~ (tổng giá trị của hình chữ nhật con từ dòng ~i_1~ đến dòng ~i_2~, từ cột 1 đến cột ~j~ của bảng ~A~)

Khi đó, lợi nhuận trở thành: $$P = F_{j_2} −F_{j_1−1} - (X_{i_2} - X_{i_1}) ∗ (Y_{j_2} - Y_{j_1})\\ = [F_{j_2} - (X_{i_2} - X_{i_1}) ∗ Y_{j_2}] - [F_{j_1−1} - (X_{i_2} - X_{i_1}) ∗ Y_{j_1}]$$

Ta duyệt ~j_2~ từ ~1~ đến ~M~. Với mỗi vị trí ~j_2~, ta chỉ cần quan tâm đến vị trí ~j_1 ≤ j_2~ sao cho ~F_{j_1−1} - (X_{i_2} - X_{i_1})∗Y_{j_1}~ nhỏ nhất. Ta có thể dễ dàng cập nhật vị trí ~j_1~ này trong ~O(1)~.

Độ phức tạp: ~O(N^2M)~