Hình chữ nhật tổng lớn nhất trong ma trận 2D | DP-27 trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về chương trình tìm hình chữ nhật có tổng lớn nhất trong ma trận 2D.

Đối với điều này, chúng tôi sẽ được cung cấp một ma trận. Nhiệm vụ của chúng ta là tìm ra ma trận con với tổng các phần tử lớn nhất của nó.

Ví dụ

#include<bits/stdc++.h>
using namespace std;
#define ROW 4
#define COL 5
//returning maximum sum recursively
int kadane(int* arr, int* start,
int* finish, int n) {
   int sum = 0, maxSum = INT_MIN, i;
   *finish = -1;
   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;
      }
   }
   if (*finish != -1)
      return maxSum;
   maxSum = arr[0];
   *start = *finish = 0;
   //finding the maximum element
   for (i = 1; i < n; i++) {
      if (arr[i] > maxSum){
         maxSum = arr[i];
         *start = *finish = i;
      }
   }
   return maxSum;
}
void findMaxSum(int M[][COL]) {
   int maxSum = INT_MIN, finalLeft, finalRight, finalTop, finalBottom;
   int left, right, i;
   int temp[ROW], sum, start, finish;
   for (left = 0; left < COL; ++left) {
      memset(temp, 0, sizeof(temp));
   for (right = left; right < COL; ++right) {
      for (i = 0; i < ROW; ++i)
         temp[i] += M[i][right];
         sum = kadane(temp, &start, &finish, ROW);
         if (sum > maxSum) {
            maxSum = sum;
            finalLeft = left;
            finalRight = right;
            finalTop = start;
            finalBottom = finish;
         }
      }
   }
   cout << "(Top, Left) (" << finalTop << ", " << finalLeft << ")" << endl;
   cout << "(Bottom, Right) (" << finalBottom << ", " << finalRight << ")" << endl;
   cout << "Max sum is: " << maxSum << endl;
}
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;
}

Đầu ra

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