2D 행렬의 최대 합 직사각형

행렬이 제공됩니다. 합이 최대인 직사각형(때로는 정사각형) 행렬을 찾아야 합니다.

이 알고리즘의 이면에 있는 아이디어는 왼쪽 및 오른쪽 열을 수정하고 각 행에 대해 왼쪽 열에서 오른쪽 열까지 요소의 합을 찾아 임시로 저장하는 것입니다. 우리는 상단 및 하단 행 번호를 찾으려고 노력할 것입니다. 임시 배열을 얻은 후 Kadane의 알고리즘을 적용하여 최대 합 하위 배열을 얻을 수 있습니다. 그것으로 전체 직사각형이 형성됩니다.

입력 및 출력

Input:
The matrix of integers.
 1  2 -1 -4 -20
-8 -3  4  2   1
 3  8  10 1   3
-4 -1   1 7  -6

Output:
The top left point and bottom right point of the submatrix, and the total sum of the submatrix.
(Top, Left) (1, 1)
(Bottom, Right) (3, 3)
The max sum is: 29

알고리즘

kadaneAlgorithm(배열, 시작, 끝, n)

입력: 배열은 합계, 시작점과 끝점, 요소 수를 보유합니다.

출력 - 시작점과 끝점을 찾으세요.

Begin
   sum := 0 and maxSum := - ∞
   end := -1
   tempStart := 0

   for each element i in the array, do
      sum := sum + array[i]
      if sum < 0, then
         sum := 0
         tempStart := i + 1
      else if sum > maxSum, then
         maxSum := sum
         start := tempStart
         end := i
   done

   if end ≠ -1, then
      return maxSum
   maxSum := array[0], start := 0 and end := 0

   for each element i from 1 to n of array, do
      if array[i] > maxSum, then
         maxSum := array[i]
         start := i and end := i
   done

   return maxSum
End

maxSumRect(행렬)

입력: 주어진 매트릭스.

출력: 직사각형의 최대 합입니다.

Begin
   maxSum := - ∞
   define temp array, whose size is same as row of matrix

   for left := 0 to number of columns in the Matrix, do
      till temp array with 0s
      for right := left to column of matrix -1, do
         for each row i, do
            temp[i] := matrix[i, right]
         done

         sum := kadaneAlgorithm(temp, start, end, number of rows)
            if sum > maxSum, then
               maxSum := sum
               endLeft := left
               endRight := right
               endTop := start
               endBottom := end
      done
   done

   display top left and bottom right corner and the maxSum
End

예시

#include<iostream>
#define ROW 4
#define COL 5
using namespace std;

int M[ROW][COL] = {
   {1, 2, -1, -4, -20},
   {-8, -3, 4, 2, 1},
   {3, 8, 10, 1, 3},
   {-4, -1, 1, 7, -6}
 };

int kadaneAlgo(int arr[], int &start, int &end, int n) {    //find max sum and starting and ending location
   int sum = 0, maxSum = INT_MIN;

   end = -1;    //at first no place is selected

   int tempStart = 0;    //starting from 0

   for (int i = 0; i < n; i++) {
      sum += arr[i];
      if (sum < 0) {
         sum = 0;
         tempStart = i+1;
      }else if (sum > maxSum) {     //get maximum sum, and update start and end index
         maxSum = sum;
         start = tempStart;
         end = i;
      }
   }

   if (end != -1)
      return maxSum;
   //when all elements are negative in the array
   maxSum = arr[0];
   start = end = 0;

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

void maxSumRect() {
   int maxSum = INT_MIN, endLeft, endRight, endTop, endBottom;

   int left, right;
   int temp[ROW], sum, start, end;

   for (left = 0; left < COL; left++) {
      for(int i = 0; i<ROW; i++)//temp initially holds all 0
         temp[i] = 0;

      for (right = left; right < COL; ++right) {
         for (int i = 0; i < ROW; ++i)    //for each row, find the sum
            temp[i] += M[i][right];
         sum = kadaneAlgo(temp, start, end, ROW);    //find sum of rectangle (top, left) and (bottom right)

         if (sum > maxSum) {    //find maximum value of sum, then update corner points
            maxSum = sum;
            endLeft = left;
            endRight = right;
            endTop = start;
            endBottom = end;
         }
      }
   }

   cout << "(Top, Left) ("<<endTop<<", "<<endLeft<<")"<<endl;
   cout << "(Bottom, Right) ("<<endBottom<<", "<<endRight<<")"<<endl;
   cout << "The max sum is: "<< maxSum;
}

int main() {
   maxSumRect();
}

출력

(Top, Left) (1, 1)
(Bottom, Right) (3, 3)
The max sum is: 29