Анонс #122. Максимальная подматрица
UniLecs
Задача: дана матрица N*M, состоящая из целых чисел. Необходимо определить подматрицу с максимальной суммой элементов в ней.
Входные данные: arr - матрица N*M, элементы матрицы целые числа по модулю меньше 1000. N,M - от 1 до 1000.
Вывод: максимальная сумма в подматрице исходной матрицы arr, а также координаты этой подматрицы.
Пример:
[ { -1, -2, -3 },
{ 1, 1, -4 },
{ 1, 1, -5 } ]
MaxSum = 4
SubMatrix Coordinate: (2, 1) - (3, 2). (Подматрица с левой верхней вершиной (2,1) и правой нижней (3,2), нумерация с 1)
P.S. Мы уже разбирали похожую задачу, но в рамках одномерного массива. Но возможно, ее разбор поможет вам. Удачи!