Понимание алгоритма Кадана для двумерного массива

Question

Понимание алгоритма Кадана для двумерного массива

Я пытаюсь написать программу, которая решает максимальная проблема подмассива. Я могу понять интуицию алгоритма Кадана на одномерном массиве, а также реализацию O (N ^ 4) на двумерном массиве. Однако у меня возникли проблемы с пониманием реализации O (N ^ 3) в двумерном массиве.

1) Почему мы добавляем элементы с элементами из предыдущих строк в одном столбце?

for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++)
array[i][j] += array[i-1][j];
}

2) у меня нет понимания второй части алгоритма

Попытка поиска объяснения в Интернете, но безрезультатно. Надеюсь получить помощь здесь!

Заранее спасибо!

2

c++java kadanes-algorithm

Решение

Другие решения

Я знаю, что это старый вопрос. Но у Google нет правильных ответов, или они перегружены.

Нет, это не правильный путь. Рабочий пример на O (N ^ 2):

  /**
* Kadane 1d
* @return max sum
*/
public static int maxSum(int[] a) {
int result = a[0]; //get first value for correct comparison
int sum = a[0];
for (int i = 1; i < a.length; i++) {
sum = Math.max(sum + a[i], a[i]); //first step getting max sum, temporary value
result = Math.max(result, sum);
}
return result;
}

/**
* Kadane 2d
* @param array
* @return max sum
*/
public static int maxSum2D(int array[][]){
int result = Integer.MIN_VALUE; //result max sum
for (int i = 0; i < array.length; i++) {
int sum = maxSum(array[i]);
result = Math.max(result, sum);
}
return result;
}

Полностью примеры:

Легко: https://pastebin.com/Qu1x0TL8
Дополненный: https://pastebin.com/Tjv602Ad
С индексами: https://pastebin.com/QsgPBfY6

1

Источник

Accepted Answer

Вы знаете, как вычислить подмассив с максимальной суммой в одномерном массиве, используя алгоритм Кадане. Теперь мы хотим расширить этот алгоритм для двумерного массива. Для алгоритма O (N ^ 3) у нас есть интуиция. Если мы каким-то образом создадим N ^ 2 подзадач, а затем попробуем запустить алгоритм O (N) Kadane, мы сможем решить проблему максимального подмассива.

Таким образом, в основном, как мы создаем подзадачи N ^ 2, перебирая все верхние и нижние строки матрицы. Затем мы пытаемся найти оптимальные столбцы, между которыми существует подмассив, применяя алгоритм 1D Кадане. Таким образом, мы суммируем числа между этими двумя строками столбцов, а затем применяем 1D-алгоритм Кадане к этому вновь сформированному 1D-массиву.

Но у нас есть проблема здесь. Вычисление сумм для всех диапазонов O (n ^ 2) верхнего и нижнего рядов само будет O (n ^ 4). Эту бутылочную горловину можно преодолеть, изменив нашу матрицу, заменив каждый элемент суммой всех чисел, которые находятся над ним в столбце этого элемента. Таким образом, теперь мы можем узнать сумму чисел между любыми двумя строками за O (n) времени, вычитая соответствующие массивы в матрице.

Псевдокод Java —

    int kadane2D(int array[N+1][M+1]){

// Modify the array's elements to now hold the sum
// of all the numbers that are above that element in its column
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++){
array[i][j] += array[i-1][j];
}
}int ans = 0;  // Holds the maximum sum matrix found till now

for(int top=1; top<=N; top++){
for(int bottom=top; bottom<=N; bottom++){
// loop over all the N^2 sub problems
int[] sums = new int[N+1];

// store the sum of numbers between the two rows
// in the sums array
for(int i=0; i<=N; i++){
sums[i] = array[bottom][i] - array[top-1][i];
}

// O(n) time to run 1D kadane's on this sums array
ans = Math.max(ans, kadane1d(sums));
}
}
return ans;
}

5