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

Я пытаюсь написать программу, которая решает проблему максимального подмассива. Я могу понять интуицию алгоритма Кадана в одномерном массиве, а также реализацию 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 ответа

Решение

Вы знаете, как вычислить подмассив с максимальной суммой в одномерном массиве, используя алгоритм Кадане. Теперь мы хотим расширить этот алгоритм для двумерного массива. Для алгоритма 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;
    }
Источник

Для людей, которые понимают алгоритм 1D Кадане, нижеследующее должно быть легко для понимания. В основном мы пытаемся преобразовать 2D-матрицу в 1D с помощьюprefix sumдля каждой строки. И для каждой строки суммы префиксов мы просто применяем 1D алгоритм Кадане.

Просто разместите рабочий код Python:

class Kadane2D:
    def maxSumRetangle(self, grid):
        def kadane1D(arr):
            curmax, maxsofar = 0, float('-inf')
            for a in arr:
                curmax = max(a, curmax + a)
                maxsofar = max(curmax, maxsofar)
            return maxsofar

        m, n, ans = len(grid), len(grid[0]), float('-inf')
        colCum = [[0] * n]
        for row in grid:
            colCum.append([pre + now for pre, now in zip(colCum[-1], row)])

        for top in range(1, m + 1):
            for bottom in range(top, m + 1):
                sums = [b - t for b, t in zip(colCum[bottom], colCum[top - 1])]
                ans = max(ans, kadane1D(sums))
        return ans


grid = [[1, 2, - 3], [3, 4, -6]]
assert Kadane2D().maxSumRetangle(grid) == 10
grid = [[1, 2, -1, -4, -20],
        [-8, -3, 4, 2, 1],
        [3, 8, 10, 1, 3],
        [-4, -1, 1, 7, -6]]
assert Kadane2D().maxSumRetangle(grid) == 29
Источник

Я знаю, что это старый вопрос. Но у 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;
  }

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

Источник
Другие вопросы по тегам