MaximumSumRectangularSubMatrix.java

/*
https://youtu.be/yCQN096CwWM
https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/SubRectangularMatrixWithMaximumSum.java

We Use Kadane's Algorithm to solve this problem
*/

classMaxSumRectangularSubMatrix{
classResult{
intmaxSum;
intleftBound;
intrightBound;
intlowBound;
intupBound;
 }

classKadaneResult{
intsum;
intstart; //will indicate the start row of the max sum sub matrix 
intend; //will indicate the end row of the max sum sub matrix
 }


publicResultmaxSum(intA[][]){ 
introws = A.length;
intcols = A[0].length;

intkadaneCol[] = newint[rows];
Resultresult = newResult();

//we set a new start boundary for the sub-matrix --> this is the left boundary
for(intleft=0 ; left < cols ; left++){

//Clear the previous values
Arrays.fill(kadaneCol,0); //O(n)

//the left boundary is set, but we move the right boundary towards the end of the matrix
for(intright=left ; right < cols ; right++){

//add values from the newly shifted right boundary
//This is done because we are applying Kadane's Algorithm which works on 1D arrays
//We pass an array(to the kadane's algorithm) containing cummulative sum of each row(which makes the array 1D)
//Kadane's algo finds the max sum subarray from this array --> This is nothing but the max sum sub matrix
//left and right are set in this function and Kadane's algo helps to fix the up and low.
for(inti=0;i<rows;i++){
kadaneCol[i] += A[i][right];
 }

//Update the current result 
KadaneResultkadaneResult = kadane(kadaneCol);
if(kadaneResult.sum > result.maxSum){
result.maxSum = kadaneResult.sum;
result.leftBound = left;
result.rightBound = right;
result.upBound = kadaneResult.start;
result.lowBound = kadaneResult.end;
 }
 }
 }

returnresult;

 }

/*
 Time Complexity - O((col^2)*row) --> cubic
 Space Complexity - O(row)
 */

publicKadaneResultkadane(intA[]){ //to return the maxSum, start and end in linear time
intn = A.length;

if(n == 0) return0;

KadaneResultkr = null;

intmaxEndingHere = A[0];
intmaxSoFar = A[0];
intmaxStart = 0;
intstart = 0;
intmaxEnd = 0;

for(inti=1 ; i < n ; i++){
//include current element in the sub-array sum
maxEndingHere+=A[i];

//check if starting a new sub-array gives a greater sum than the current sum
if(maxEndingHere < A[i]){
start = i;
maxEndingHere = A[i];
 }

//update the overall max-sum
if(maxSoFar < maxEndingHere){
maxSoFar = maxEndingHere;
maxEnd = i;
maxStart = start;
 }
 }

returnnewKadaneResult(maxSoFar, maxStart, maxEnd);
 }

}