Двумерный максимальный подмассив

Question

Bentley's Programming Pearls (2-е изд.) В главе о проблеме максимального подмассива описывает его двумерную версию:

... нам дан массив n × n , и мы должны найти максимальную сумму, содержащуюся в любом прямоугольном подмассиве. В чем сложность этой проблемы?

Бентли отмечает, что на дату публикации книги (2000 г.) проблема поиска оптимального решения была открытой.
Это все еще так? Какое решение является самым известным? Любой указатель на недавнюю литературу?

Answer 1

1D решение этой проблемы (максимальный подмассив) - это Theta (n), использующий алгоритм, называемый «алгоритм Кадана» (я уверен, что есть и другие алгоритмы, но у меня есть личный опыт работы с этим). Известно, что двумерное решение этой проблемы (максимальный под прямоугольник) - O (n ^ 3) с использованием реализации алгоритма Кадане (опять же, я уверен, что есть и другие, но я использовал это раньше).

Хотя мы знаем, что двумерное решение можно найти в тэте (n ^ 3), никто не смог доказать, является ли n ^ 3 нижней границей. Для многих алгоритмов, когда вы увеличиваете размерность, вы увеличиваете нижнюю границу алгоритма на постоянную величину. С этой конкретной проблемой сложность не увеличивается линейно, и поэтому нет никакого известного решения для работы для любого данного измерения, таким образом, проблема все еще остается открытой.

В отношении аналогичного случая: мы знаем, что 2 матрицы могут быть умножены вместе в n ^ 3 раза. Существует также алгоритм, который может сделать это в п ^ 2,8, я считаю. Тем не менее, нет математики, указывающей, что мы не можем получить его ниже, чем n ^ 2.8, так что это все еще «открытый» алгоритм.

Answer 2

   // Program to find maximum sum subarray in a given 2D array
#include <stdio.h>
#include <string.h>
#include <limits.h>
#define ROW 4
#define COL 5

  // Implementation of Kadane's algorithm for 1D array. The function returns the
// maximum sum and stores starting and ending indexes of the maximum sum subarray
// at addresses pointed by start and finish pointers respectively.
int kadane(int* arr, int* start, int* finish, int n)
{
// initialize sum, maxSum and
int sum = 0, maxSum = INT_MIN, i;

// Just some initial value to check for all negative values case
*finish = -1;

// local variable
int local_start = 0;

for (i = 0; i < n; ++i)
{
    sum += arr[i];
    if (sum < 0)
    {
        sum = 0;
        local_start = i+1;
    }
    else if (sum > maxSum)
    {
        maxSum = sum;
        *start = local_start;
        *finish = i;
    }
}

 // There is at-least one non-negative number
if (*finish != -1)
    return maxSum;

// Special Case: When all numbers in arr[] are negative
maxSum = arr[0];
*start = *finish = 0;

// Find the maximum element in array
for (i = 1; i < n; i++)
{
    if (arr[i] > maxSum)
    {
        maxSum = arr[i];
        *start = *finish = i;
    }
   }
   return maxSum;
 }

 // The main function that finds maximum sum rectangle in M[][]
  void findMaxSum(int M[][COL])
 {
 // Variables to store the final output
 int maxSum = INT_MIN, finalLeft, finalRight, finalTop, finalBottom;

 int left, right, i;
 int temp[ROW], sum, start, finish;

  // Set the left column
   for (left = 0; left < COL; ++left)
  {
     // Initialize all elements of temp as 0
    memset(temp, 0, sizeof(temp));

    // Set the right column for the left column set by outer loop
    for (right = left; right < COL; ++right)
    {
        // Calculate sum between current left and right for every row 'i'
        for (i = 0; i < ROW; ++i)
            temp[i] += M[i][right];

        // Find the maximum sum subarray in temp[]. The kadane() function
        // also sets values of start and finish.  So 'sum' is sum of
        // rectangle between (start, left) and (finish, right) which is the
        //  maximum sum with boundary columns strictly as left and right.
        sum = kadane(temp, &start, &finish, ROW);

        // Compare sum with maximum sum so far. If sum is more, then update
        // maxSum and other output values
        if (sum > maxSum)
        {
            maxSum = sum;
            finalLeft = left;
            finalRight = right;
            finalTop = start;
            finalBottom = finish;
        }
     }
   }

  // Print final values
  printf("(Top, Left) (%d, %d)\n", finalTop, finalLeft);
  printf("(Bottom, Right) (%d, %d)\n", finalBottom, finalRight);
  printf("Max sum is: %d\n", maxSum);
  }

  // Driver program to test above functions
  int main()
  {
  int M[ROW][COL] = {{1, 2, -1, -4, -20},
                   {-8, -3, 4, 2, 1},
                   {3, 8, 10, 1, 3},
                   {-4, -1, 1, 7, -6}
                  };

  findMaxSum(M);

 return 0;
 }


  ////////I found this program , hope it will help you

Answer 3

К вашему сведению, у нового издания книги есть ответ, но он настолько расплывчатый, что я не знаю, к чему это приведет.

В любом случае, я бы использовал «разделяй и властвуй» + динамическое программированиечтобы решить это.Определим MaxSum (x, y) как максимальную сумму любого подмассива внутри прямоугольника, ограниченного самым верхним левым углом массива NXN, с высотой y и шириной x.(поэтому ответ на вопрос будет в MaxSum (n-1, n-1))

MaxSum(x, y) is the max between:
1) MaxSum(x, y-1)
2) MaxSum(x-1, y)
3) Array[x, y] (the number in this N X N array for this specific location)
4) MaxEnding(x, y-1) + SUM of all elements from Array[MaxEndingXStart(x, y-1), y] to Array[x, y]
5) MaxEnding(x-1, y) + SUM of all elements from Array[x, MaxEndingYStart(x-1, y)] to Array[x, y]

MaxEnding (x, y-1) - максимальная сумма любого подмассива, который ВКЛЮЧАЕТ # вМассив [x, y-1].Аналогично, MaxEnding (x-1, y) - это максимальная сумма любого подмассива, который ВКЛЮЧАЕТ # в массиве [x-1, y].MaxEndingXStart (x, y-1) - это НАЧАЛЬНАЯ координата x подмассива, который имеет максимальную сумму любого подмассива, включающего # в массив [x, y-1].MaxEndingYStart (x-1, y) - это начальная координата y подмассива, который имеет максимальную сумму любого подмассива, включающего # в массив [x-1, y].

2 сумма в # 4и # 5 ниже можно легко вычислить, сохраняя сумму всех элементов, встречающихся в определенной строке, по мере прохождения каждого столбца, а затем вычитая 2 суммы, чтобы получить сумму для определенного раздела.

Для реализации этого, вам нужно будет сделать восходящий подход, так как вам нужно вычислить Max (x, y-1), Max (x-1, y), MaxEnding (x, y-1) и MaxEnding (x-1), у) .. так что вы можете делать поиск при вычислении MaxEnding (х, у).

//first do some preprocessing and store Max(0, i) for all i from 0 to n-1.
//and store Max(i, 0) for all i from 0 to n-1.

for(int i =1; i < n; i++){
   for(int j=1; j < n; j++) {
      //LOGIC HERE
   }
}