Ta duyệt qua tọa độ \(y\) và tọa độ \(v\) của các HCN con cần xét.

Đặt \(b(x) = min(a_{r,x})\) và \(c(x) = \sum a_{r,x}\) với \(y \le r \le v\).
Bài toán đưa về : tìm max của biểu thức \(F(l,r) = min(b_i) * \sum c_i\) với \(l \le i \le r\), hai số \(l,r\) bất kì thỏa \(1 \le l \le r \le n\).

Để tính biểu thức này, tại mỗi vị trí \(b_i\) ta cần tìm \(L_i\) và \(R_i\), \(L_i\) nhỏ nhất có thể, \(R_i\) lớn nhất có thể, sao cho : \(min(b[L_i \rightarrow R_i]) = b_i\). Sau đó cập nhật đáp án với giá trị \(b_i \times \sum c[L_i \rightarrow R_i]\). \(L_i, R_i\) có thể dùng Stack để tìm.

Độ phức tạp \(O(n^3)\)