Tổng hình chữ nhật lớn nhất

Buổi 04 — Mảng 2D & Chuỗi Dynamic Programming
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
matrix
Submissions
Đề bài

Cho ma trận số nguyên $A$ kích thước $M \times N$ (có thể chứa số âm, số $0$ và số dương). Hãy tìm ma trận con hình chữ nhật khác rỗng có tổng các phần tử lớn nhất và in ra tổng lớn nhất đó.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên dương $M, N$.
  • $M$ dòng tiếp theo, mỗi dòng chứa $N$ số nguyên.
Dữ liệu ra

Một số nguyên duy nhất là tổng lớn nhất của một ma trận con khác rỗng.

Ví dụ
Input Output
4 5
1 2 -1 -4 -20
-8 -3 4 2 1
3 8 10 1 3
-4 -1 1 7 -6
29
Giới hạn

$1 \le M, N \le 300$, $|A_{i,j}| \le 10^6$.

Draft saved