Elearning CodePath – CTP Online Judge

Tổng Con Hình chữ nhật Lớn nhất

GEN014

🟢 Easy #General #Prefix Sum #Dynamic Programming

### 📌 Thông tin chung

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

Cho một mảng hai chiều $A$ kích thước $M \times N$ gồm các số nguyên.

Yêu cầu: Tìm một **bảng con (hình chữ nhật con)** trong lưới sao cho **tổng các số nguyên** của các ô nằm trong nó là **lớn nhất**.

Bảng con được xác định bởi hai hàng $r_1, r_2$ ($1 \le r_1 \le r_2 \le M$) và hai cột $c_1, c_2$ ($1 \le c_1 \le c_2 \le N$). Tổng cần tìm là:
$\text{Max Sum} = \max_{1 \le r_1 \le r_2 \le M, 1 \le c_1 \le c_2 \le N} \left( \sum_{i=r_1}^{r_2} \sum_{j=c_1}^{c_2} A_{i, j} \right)$

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

Dữ liệu vào từ file `SUMREC.INP`:

* Dòng 1: Ghi hai số nguyên dương $M$ (số hàng) và $N$ (số cột).
* $M$ dòng tiếp theo: Dòng thứ $i$ ghi $N$ số nguyên mô tả hàng thứ $i$ của bảng.

Giới hạn:
* $1 \le M, N \le 100$.
* Giá trị các phần tử $A_{i, j}$ nằm trong phạm vi số nguyên 32-bit.

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

Ghi ra file `SUMREC.OUT` một số nguyên duy nhất là tổng lớn nhất tìm được.

---
### ✨ Ví dụ

| Input (`SUMREC.INP`) | Output (`SUMREC.OUT`) |
| :--- | :--- |
| `4 5` <br> `-3 2 4 -7 -12` <br> `-1 2 3 -10 -8` <br> `-5 1 1 -6 -9` <br> `-2 5 8 -4 -3` | `26` |

---
### 🏷 Subtask

| Subtask | Ràng buộc | Điểm |
| :--- | :--- | :--- |
| 1 | $M, N \le 50$ | $40\%$ |
| 2 | $M, N \le 100$ | $60\%$ |

---

✅ Đã AC: 0 / 0 submissions