Вот объяснение того, чтобы пойти с публикуемым кодом. Для эффективного выполнения этой работы есть два ключевых метода: (I) алгоритм Кандана и (II) с использованием префиксных сумм. Вам также необходимо (III) применить трюки к матрице.
Часть I: алгоритм Kandane в
алгоритм Kandane является способом найти непрерывную подпоследовательность с максимальной суммой. Давайте начнем с подхода грубой силы для нахождения максимальной непрерывной подпоследовательности, а затем рассмотрим ее оптимизацию для получения алгоритма Кандана.
Предположим, у вас есть последовательность:
-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: Приведение трюки вместе, чтобы найти Макса подматрица
Предположим, что вы знаете, верхний и нижний ряд максимальной подматрицы. Вы могли бы сделать это:
- Игнорировать строки выше верхнего ряда и игнорировать ряды внизу внизу. строка.
- С какой матрицей осталось считать сумму использования каждого столбца в , чтобы сформировать последовательность (вроде строки, которая представляет несколько строк). (Вы можете быстро вычислить любой элемент этой последовательности с использованием префикса .)
- Используйте подход Кандана, чтобы найти лучшую подпоследовательность в этой последовательности . Вы получите указатели слева и справа позиции лучшей подматрицы.
А как насчет фактического определения верхнего и нижнего ряда? Просто попробуйте все возможности. Попытайтесь положить верх в любом месте, где можете, и поместив его в любом месте, и запустите процедуру Kandane-base, описанную ранее для каждой возможности. Когда вы находите максимальное значение, вы отслеживаете верхнее и нижнее положение.
Поиск строки и столбца принимает O (M^2), где M - количество строк. Поиск столбца принимает O (N) время, где N - количество столбцов. Таким образом, общее время равно O (M^2 * N). И, если M = N, требуется время O (N^3).
Под «n-мерным» я предполагаю, что вы имеете в виду двумерный. N * N, а не N^n. – Kobi
Да Коби, я имел в виду 2-мерную (матрицу), извините за эту опечатку. – guirgis
Как насчет размера подматрицы? Может ли это быть чем угодно? –