Вот пояснение к опубликованному коду. Есть два ключевых трюка для эффективной работы: (I) алгоритм Кадане и (II) использование префиксных сумм. Вам также необходимо (III) применить трюки к матрице.
Часть I: алгоритм Кадане
Алгоритм Кадане - это способ найти непрерывную подпоследовательность с максимальной суммой. Давайте начнем с подхода грубой силы для нахождения максимальной непрерывной подпоследовательности, а затем рассмотрим его оптимизацию для получения алгоритма Кадане.
Предположим, у вас есть последовательность:
-1, 2, 3, -2
Для подхода грубой силы, пройдите по последовательности, генерируя все возможные подпоследовательности, как показано ниже. Учитывая все возможности, мы можем начинать, расширять или заканчивать список с каждым шагом.
At index 0, we consider appending the -1
-1, 2, 3, -2
^
Possible subsequences:
-1 [sum -1]
At index 1, we consider appending the 2
-1, 2, 3, -2
^
Possible subsequences:
-1 (end) [sum -1]
-1, 2 [sum 1]
2 [sum 2]
At index 2, we consider appending the 3
-1, 2, 3, -2
^
Possible subsequences:
-1, (end) [sum -1]
-1, 2 (end) [sum -1]
2 (end) [sum 2]
-1, 2, 3 [sum 4]
2, 3 [sum 5]
3 [sum 3]
At index 3, we consider appending the -2
-1, 2, 3, -2
^
Possible subsequences:
-1, (end) [sum -1]
-1, 2 (end) [sum 1]
2 (end) [sum 2]
-1, 2 3 (end) [sum 4]
2, 3 (end) [sum 5]
3, (end) [sum 3]
-1, 2, 3, -2 [sum 2]
2, 3, -2 [sum 3]
3, -2 [sum 1]
-2 [sum -2]
Для этого подхода грубой силы мы наконец выбираем список с лучшей суммой (2, 3), и это ответ. Однако, чтобы сделать это эффективным, учтите, что вам действительно не нужно хранить каждый из списков. Из списков, которые еще не закончились, вам нужно только сохранить лучший, остальные не могут быть лучше. Из списков, которые закончились, вам может потребоваться сохранить только лучший, и только если он лучше, чем списки, которые еще не закончились.
Таким образом, вы можете отслеживать то, что вам нужно, просто с помощью массива позиций и массива сумм. Массив позиции определяется следующим образом: position[r] = s отслеживает список, который заканчивается на r и начинается с s. И sum[r] дает сумму для подпоследовательности, заканчивающейся на index r. Это оптимизированный подход - алгоритм Кадане.
Повторное прохождение примера, отслеживая наш прогресс следующим образом:
At index 0, we consider appending the -1
-1, 2, 3, -2
^
We start a new subsequence for the first element.
position[0] = 0
sum[0] = -1
At index 1, we consider appending the 2
-1, 2, 3, -2
^
We choose to start a new subsequence because that gives a higher sum than extending.
position[0] = 0 sum[0] = -1
position[1] = 1 sum[1] = 2
At index 2, we consider appending the 3
-1, 2, 3, -2
^
We choose to extend a subsequence because that gives a higher sum than starting a new one.
position[0] = 0 sum[0] = -1
position[1] = 1 sum[1] = 2
position[2] = 1 sum[2] = 5
Again, we choose to extend because that gives a higher sum that starting a new one.
-1, 2, 3, -2
^
position[0] = 0 sum[0] = -1
position[1] = 1 sum[1] = 2
position[2] = 1 sum[2] = 5
positions[3] = 3 sum[3] = 3
Опять же, лучшая сумма равна 5, а список - от индекса 1 до индекса 2 (2, 3).
Часть II: Префиксные суммы
Мы хотим иметь способ для вычисления суммы по строке для любой начальной точки к любой конечной точке. Я хочу вычислить эту сумму за время O (1), а не просто сложить, что занимает время O (m), где m - количество элементов в сумме. С некоторым предварительным вычислением это может быть достигнуто. Вот как. Предположим, у вас есть матрица:
a d g
b e h
c f i
Вы можете предварительно вычислить эту матрицу:
a d g
a+b d+e g+h
a+b+c d+e+f g+h+i
Как только это будет сделано, вы можете получить сумму, проходящую по любому столбцу от любого начала до конечной точки в столбце, просто вычитая два значения.
Часть III: Объединение трюков, чтобы найти максимальную подматрицу
Предположим, что вы знаете верхний и нижний ряд максимальной подматрицы. Вы можете сделать это:
- Игнорировать строки над верхней строкой и игнорировать строки под нижней
строки.
- С какой матрицей осталось, рассмотрите использование суммы каждого столбца для
сформировать последовательность (вроде как строка, которая представляет несколько строк).
(Вы можете быстро вычислить любой элемент этой последовательности с префиксом
Суммы приближаются.)
- Используйте подход Кадане, чтобы выяснить лучшую подпоследовательность в этом
последовательность. Индексы, которые вы получите, покажут вам левую и правую
позиции лучшей подматрицы.
А как насчет вычисления верхнего и нижнего ряда? Просто попробуйте все возможности. Попробуйте установить верхнюю часть везде, где можете, а нижнюю - везде, где можете, и выполните описанную выше процедуру базы Kadane для каждой возможности. Когда вы найдете максимум, вы отслеживаете верхнюю и нижнюю позиции.
Нахождение строки и столбца занимает O (M ^ 2), где M - количество строк. Поиск столбца занимает O (N) времени, где N - количество столбцов. Таким образом, общее время составляет O (M ^ 2 * N). И, если M = N, требуется время O (N ^ 3).