Нахождение максимальной суммы суб = прямоугольник внутри матрицы

Question

Можно создать дубликат:
Getting the submatrix with maximum sum?

Учитывая 2-мерный массив положительных и отрицательных целых чисел, найти суб-прямоугольник самая большая сумма. Сумма прямоугольника - это сумма всех элементов этого прямоугольника. В этой задаче суб-прямоугольник с наибольшей суммой называется максимальным суб-прямоугольником. Суб-прямоугольник - это любой смежный суб-массив размером 1 * 1 или выше, расположенный во всем массиве. В качестве примера, максимальный суб-прямоугольник массива:

0 -2 -7 0 
9 2 -6 2 
-4 1 -4 1 
-1 8 0 -2 

находится в нижнем левом углу:

9 2 
-4 1 
-1 8 

и имеет сумму 15

Так дал прямоугольник, что будет эффективным алгоритмом для нахождения суммы максимального суб-прямоугольника (15 в приведенном выше примере).

Answer 1

Вы можете решить это в O(numCols*numLines^2). Рассмотрим ту же проблему в 1d:

Для вектора из n элементов найдите непрерывную непрерывную подпоследовательность.

Let S[i] = maximum sum contiguous subsequence that ends with element i. У нас есть S[1] = array[1] и S[i > 1] = max(S[i - 1] + array[i], array[i]).

Обратите внимание, что вам не нужен вектор, чтобы решить эту проблему, достаточно двух переменных. Подробнее here.

Теперь, для вашего матричного корпуса, вычислите Sum[i][j] = sum of the first i elements of column j.

Теперь, для каждой возможной пары строк в вашей матрице примените 1d-алгоритм к «вектору», сделанному из элементов между строками вашей текущей пары.