Cho một ma trận kích thước gồm các số nguyên dương. Các hàng được đánh số từ đến từ trên xuống dưới, các cột được đánh số từ đến từ trái sang phải. Giá trị của ô tại hàng , cột là .
Nhiệm vụ của bạn là tìm một hình chữ nhật con (sub-rectangle) của ma trận đã cho sao cho hình chữ nhật con này thỏa mãn hai điều kiện sau:
Trên mỗi hàng thuộc hình chữ nhật con, các giá trị tăng dần hoặc bằng nhau (không giảm) theo chiều từ trái sang phải.
Trên mỗi cột thuộc hình chữ nhật con, các giá trị tăng dần hoặc bằng nhau (không giảm) theo chiều từ trên xuống dưới.
Hãy tìm diện tích (số lượng ô) lớn nhất của hình chữ nhật con thỏa mãn các điều kiện trên.
Dữ liệu:
Dòng đầu chứa hai số nguyên dương và (kích thước của ma trận).
dòng tiếp theo, dòng thứ chứa số nguyên dương .
Hai số liên tiếp trên một dòng được ghi cách nhau một dấu cách.
Kết quả:
Một số nguyên dương duy nhất là diện tích lớn nhất của hình chữ nhật con tìm được.
Ví dụ:
Dữ liệu:
3 4
9 2 4 8
3 5 7 8
6 8 1 3
Kết quả:
6
Giải thích: Hình chữ nhật con thỏa mãn lớn nhất có góc trái trên là với giá trị , góc phải dưới là với giá trị . Các phần tử trong hình chữ nhật này là:
Thỏa mãn tính chất không giảm trên hàng và cột. Tổng diện tích là .
