Ma trận con tổng lớn nhất

Arrays Buổi 15 — Prefix Sum & Difference Array prefix-sum
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Submissions
Đề bài

Cho ma trận số nguyên kích thước $N \times M$ (có thể chứa số âm). Hãy tìm tổng lớn nhất của một ma trận con hình chữ nhật không rỗng nằm bên trong ma trận đã cho.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N, M$. $N$ dòng tiếp theo, mỗi dòng chứa $M$ số nguyên.

Dữ liệu ra

In ra một số nguyên duy nhất là tổng lớn nhất tìm được.

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
2 2
-5 -2
-3 -4
-2
Giới hạn

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

Draft saved