Prem_1997
10/4/2018 - 7:18 PM

## max_sum rectangle in an array

``````#include <bits/stdc++.h>
using namespace std;
#define ROW 4
#define COL 5
int kadane(int* arr, int* start, int* finish, int n){
int sum = 0, maxSum = INT_MIN, i;
*finish = -1;
int local_start = 0;
for(int i = 0;i < n;i++){
sum += arr[i];
if(sum < 0){
sum = 0;
local_start = i+1;
}
if(sum > maxSum){
maxSum = sum;
*start  = local_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 << finalLeft << " "<< finalRight << endl;
cout << finalTop << " " <<finalBottom << endl;

cout <<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;
}
``````