Elearning CodePath – CTP Online Judge

Hình chữ nhật Phân biệt Lớn nhất

DP001

🟢 Easy #Dynamic Programming #Combinatorics #Array

### 📌 Thông tin chung

---
### 📝 Định nghĩa Hình chữ nhật Thỏa mãn

Cho một bảng hình chữ nhật kích thước $M \times N$, ô $(i, j)$ chứa số nguyên $A_{ij}$. Cần tìm một hình chữ nhật (tập hợp các ô $(i, j)$ với $r_1 \le i \le r_2$ và $c_1 \le j \le c_2$) có **diện tích lớn nhất** thỏa mãn:

1.  Cạnh song song với cạnh bảng.
2.  Các số ghi trong các ô thuộc hình chữ nhật được chọn phải hoàn toàn phân biệt.

---
### 📝 Bài toán

Tìm diện tích $Area = (r_2 - r_1 + 1) \times (c_2 - c_1 + 1)$ lớn nhất của hình chữ nhật con thỏa mãn điều kiện các phần tử bên trong là phân biệt.

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ tệp tin văn bản `BANGHCN.INP` gồm:

* Dòng 1 chứa hai số nguyên dương $M, N$ (kích thước bảng).
* $M$ dòng tiếp theo, dòng thứ $i$ chứa $N$ số nguyên dương, số thứ $j$ là $A_{ij}$.

Giới hạn:
* $M, N \le 100$.
* $A_{ij} \le 10^6$.

Ràng buộc:
* 30% điểm: $M, N \le 20$.
* 30% điểm: $10 \le M, N \le 100$.

---
### 📤 Định dạng Đầu ra

Ghi ra tệp tin văn bản `BANGHCN.OUT` một số nguyên duy nhất là diện tích hình chữ nhật được chọn theo phương án tìm được.

---
### ✨ Ví dụ

| BANGHCN.INP | BANGHCN.OUT |
| :---: | :---: |
| `3 3` <br> `1 3 1` <br> `4 5 6` <br> `2 6 1` | `6` |

✅ Đã AC: 0 / 0 submissions