fork download
copy 
  1. // C++ program Maximum sum rectangle in a 2D matrix.
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. // Kadane's algorithm to find the maximum sum 
  7. // subarray in a 1D array
  8. int kadaneAlgorithm(vector<int>& temp) {
  9.       int rows = temp.size();
  10.     int currSum = 0;
  11.     int maxSum = INT_MIN;
  12.  
  13.     for (int i = 0; i < rows; i++) {
  14.         currSum += temp[i];
  15.  
  16.         // Update maxSum if the current sum is greater
  17.         if (maxSum < currSum) {
  18.             maxSum = currSum;
  19.         }
  20.  
  21.         // If the current sum becomes negative, reset it to 0
  22.         if (currSum < 0) {
  23.             currSum = 0;
  24.         }
  25.     }
  26.  
  27.     return maxSum;
  28. }
  29.  
  30. // Function to find the maximum sum rectangle in a 2D matrix
  31. int maxSumRectangle(vector<vector<int>> &mat) {
  32.     int rows = mat.size();
  33.     int cols = mat[0].size();
  34.  
  35.     int maxSum = INT_MIN;
  36.  
  37.     // Initialize a temporary array to store row-wise
  38.       // sums between left and right boundaries
  39.     vector<int> temp(rows);
  40.  
  41.     // Check for all possible left and right boundaries
  42.     for (int left = 0; left < cols; left++) {
  43.  
  44.         // Reset the temporary array for each new left boundary
  45.         for (int i = 0; i < rows; i++)
  46.             temp[i] = 0;
  47.  
  48.         for (int right = left; right < cols; right++) {
  49.  
  50.             // Update the temporary array with the current
  51.               // column's values
  52.             for (int row = 0; row < rows; row++) {
  53.                 temp[row] += mat[row][right];
  54.             }
  55.  
  56.             // Find the maximum sum of the subarray for the 
  57.               // current column boundaries
  58.             int sum = kadaneAlgorithm(temp);
  59.  
  60.             // Update the maximum sum found so far
  61.             maxSum = max(maxSum, sum);
  62.         }
  63.     }
  64.  
  65.     return maxSum;
  66. }
  67.  
  68. int main() {
  69.     vector<vector<int>> mat = {{1, 2, -1, -4, -20},
  70.                                {-8, -3, 4, 2, 1}, 
  71.                                {3, 8, 10, 1, 3},
  72.                                {-4, -1, 1, 7, -6}};
  73.  
  74.     int res = maxSumRectangle(mat); 
  75.     cout << res << endl;             
  76.  
  77.     return 0;
  78. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
29
https://ideone.com/3BGGgI
language:
C++14 (gcc 8.3)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!