Bài toán yêu cầu tính hình chữ nhật lớn nhất mà đơn sắc và có cạnh song song với trục ngang dọc. Lời giải này gồm các nội dung sau:

• Tính hình chữ nhật lớn nhất màu vàng:
  1. Ý tưởng: duyệt tất cả hcn, tham lam hcn lớn nhất
  2. Cài đặt ý tưởng
• Đảo ngược màu và gọi lại hàm Tính, lấy giá trị tối đa.

Ý tưởng

Xét một ví dụ như bên dưới hình. Ứng với mỗi cột \(i\), ta có thể tạo hình chữ nhật rộng \(1\) đơn vị bằng cách bắt đầu từ đỉnh của cột \(i\) và lên đến cao nhất là \(m\).

Với $i=4$

Nhận xét rằng, ta có thể mở rộng hình chữ nhật lên này sang hai bên xa nhất có thể, cho đến khi đụng phải cột khác hoặc đụng biên của bảng:

Đây là hình chữ nhật lớn nhất, với cạnh đáy chạm cột $i=4$

Nếu với mỗi cột \(i\), ta tính được vị trí \(L\) là vị trí gần nhất bên trái \(i\) mà độ cao cột \(L\) cao hơn cột \(i\), và ta tính được vị trí \(R\) là vị trí gần nhất bên phải \(i\) mà độ cao cột \(R\) cao hơn cột \(i\), ta cũng sẽ tính được diện tích hình chữ nhật như đã nói.

Chiều cao là $5$, chiều rộng là $4$, diện tích là $20$

Cụ thể hơn, diện tích đó được tính bằng $ (R-L-1)*(m-H_i) $, với:

• \(L\) lớn nhất và \(L < i, H_L > H_i\)
• \(R\) bé nhất và \(i < R, H_i < H_R\)

Tóm lại, sử dụng mỗi cột \(i\) để xác định tất cả hình chữ nhất, và sử dụng tham lam để lấy hình chữ nhật lớn nhất.

Cài đặt

Để tính được \(L, R\) với mỗi \(i\), ta sẽ duyệt qua \(R\) và tính \(i\) và \(L\) bằng một Ngăn xếp như sau. Xét ví dụ khi nãy, \(t_1\) là phần tử trên cùng stack, \(t_2\) là phần tử thứ \(2\) trên stack, còn \(i\) ta sẽ duyệt. Trong khi \(t_1 \leq i\), ta sẽ tính hình chữ nhật lớn nhất với cột \(t_1\), lưu đáp án và pop. Ngược lại, nếu \(t_1 > i\) ta sẽ thêm \(i\) vào stack và duyệt tiếp \(i\).

Và để đỡ phải if các điều kiện biên, ta có thể gán \(H_0 = m+1\) và \(H_{n+1} = m+2\).

Đảo ngược màu

Sau khi tính được hình chữ nhật có màu vàng, ta chỉ cần đảo ngược giá trị của cột bằng cách gán cột \(i\) cho giá trị là \(m-H_i\). Sau đó, gọi lại hàm tính.

Vì hcn phải đơn sắc, nếu là màu này thì các cột phải là màu khác, nên ta có thể đảo ngược như vậy.