Ý tưởng

Dùng mảng cộng dồn hai chiều để lấy tổng mọi hình vuông cạnh ~2k+1~ trong ~O(1)~. Với mỗi ô có thể làm tâm, kiểm tra xem trong hình vuông quanh nó có ô nào lớn hơn hoặc bằng giá trị tâm hay không. Khi gặp ô vi phạm có thể dừng kiểm tra tâm hiện tại. Với ~k \le 20~, cách này đủ tốt khi cài đặt cẩn thận; có thể tối ưu thêm bằng kỹ thuật hàng đợi đơn điệu hai chiều để lấy cực đại vùng.

Độ phức tạp

Bản trực tiếp có độ phức tạp ~O(nm(2k+1)^2)~ với dừng sớm; bản tối ưu cực đại vùng đạt ~O(nm)~.