Ma trận con tổng lớn nhất
Points
45
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Đề 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$.
Community Discussion