Prerequisite

Maximum Sum Subarray (Kadane's Algorithm)

Problem Statement

Given a 2D matrix M of dimensions RxC. Find the maximum sum subarray in it.

Example 1:

Input:
R=4
C=5
M=[[1,2,-1,-4,-20],
[-8,-3,4,2,1],
[3,8,10,1,3],
[-4,-1,1,7,-6]]
Output:
29
Explanation:
The matrix is as follows and the
blue rectangle denotes the maximum sum
rectangle.

Problem Link

Maximum sum Rectangle | Practice | GeeksforGeeks

Code

class Solution {
  public:
  
  int kadane(vector<int> &nums) {
      int gm = INT_MIN,lm =0;
      
      for(int ele:nums) {
          lm = max(ele,ele+lm);
          gm = max(lm,gm);
      }
      return gm;
  }
    int maximumSumRectangle(int R, int C, vector<vector<int>> M) {
       
       int res = INT_MIN;
       
       for(int i=0;i<R;i++) {
           vector<int> temp(C,0);
           for(int j=i;j<R;j++) {
               
               for(int k=0;k<C;k++) {
                   temp[k]+=M[j][k];
               }
               int gm = kadane(temp);
               res = max(res,gm);
           }
       }
       return res;
    }
};
// Time Complexity: O(n^2)

Similar problems

Largest rectangular sub-matrix whose sum is 0 - GeeksforGeeks

Largest area rectangular sub-matrix with equal number of 1's and 0's - GeeksforGeeks