Максимальная подматрица
Дана матрица размера , состоящая из целых чисел. Нужно определить подматрицу с наибольшей суммой элементов.
Входные данные
В первой строке указаны два целых числа — количество строк матрицы
r и количество столбцов c (1 ≤ r, c ≤ 50).Далее следует
r строк, в каждой из которых содержится по c целых чисел, разделённых пробелом. Эти числа являются элементами матрицы ().Выходные данные
Требуется вывести одно целое число — максимально возможную сумму в подматрице.
Примеры
Входные данные | Выходные данные |
3 5
1 2 -3 4 -6
-1 3 -100 4 0
0 1 -2 0 100 | 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