Максимальная подматрица
Дана матрица размера , состоящая из целых чисел. Нужно определить подматрицу с наибольшей суммой элементов.
Входные данные
В первой строке указаны два целых числа — количество строк матрицы r и количество столбцов c (1 ≤ r, c ≤ 50).
Далее следует r строк, в каждой из которых содержится по c целых чисел, разделённых пробелом. Эти числа являются элементами матрицы ().
Выходные данные
Требуется вывести одно целое число — максимально возможную сумму в подматрице.
Примеры
Входные данные | Выходные данные |
|---|---|
3 5 | 104 |
Пояснение
1 | 2 | -3 | 4 | -6 |
-1 | 3 | -100 | 4 | 0 |
0 | 1 | -2 | 0 | 100 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB