# Maximum sum subrectangle using Kadane's algorithm

The idea behind this dynamic programming approach is as below.

• Get all subrectangles between the left column ( Range [ 0 .. last column ] ) and the right column ( Range [ left column + 1 .. last column ] ).
• Convert every subrectangle between the left column and the right column into a 1-dimensional array ( single column ) by adding all the numbers in a row.
• Pass the 1-dimensional array to Kadane’s algorithm for finding the maximum sum subrectangle in O ( n ) time.

Consider the below example

Forming all subrectangles between the left-most column and the right-most column takes O ( n2 ), and for every subrectangle thus formed, we run Kadane’s algorithm in O ( n ) time. Thus the overall time complexity is O ( n3 ).

Time complexity : O ( n3 ).

``````#!/usr/bin/python3
from typing import List # For annotations

def Maxsum_Kadanes (array : List[int]) -> int :

maxsum_at_current_pos = 0
maxsum_overall = 0

for num in array:
maxsum_at_current_pos = num + maxsum_at_current_pos
if (maxsum_at_current_pos > maxsum_overall):
maxsum_overall = maxsum_at_current_pos
elif (maxsum_at_current_pos < 0):
maxsum_at_current_pos = 0

return maxsum_overall

def GetMaxSumRectangle (matrix : List[List[int]]) :

rows = len (matrix)
cols = len (matrix[0])

maxsum = 0

for left_edge in range (cols) :

rectangle_in_between = [0] * rows

for right_edge in range (left_edge, cols) :

for r in range (rows) :
rectangle_in_between[r] += matrix[r][right_edge]

maxsum = max ( maxsum, Maxsum_Kadanes (rectangle_in_between) )

print("Maximum sum in sub-rectangle: " + str(maxsum))

matrix1 = [[  1, -2, -6, 0 ],
[  9,  3, -5, 3 ],
[ -5,  1, -4, 1 ],
[ -3,  7,  0,-3 ],
]
GetMaxSumRectangle(matrix1)

matrix2 = [[ 8, -2, -6, 11 ],
[ 9, -4, -5, -3 ],
[-5, -16, 14,-1 ],
[-3, -7, -1, 13 ],
]
GetMaxSumRectangle(matrix2)
``````

Output

``````Maximum sum in sub-rectangle: 12
Maximum sum in sub-rectangle: 25
``````
``````#include<iostream>
#include<vector>

using namespace std;

int maxsum_at_current_pos = 0;
int maxsum_overall = 0;

for (auto& num : array) {

maxsum_at_current_pos = num + maxsum_at_current_pos;

if (maxsum_at_current_pos > maxsum_overall) {
maxsum_overall = maxsum_at_current_pos;
} else if (maxsum_at_current_pos < 0) {
maxsum_at_current_pos = 0;
}
}
return maxsum_overall;
}

void GetMaxSumRectangle (vector<vector<int>> & matrix) {

int rows = matrix.size();
int cols = matrix[0].size();

int maxsum = 0;

for (int left_edge = 0; left_edge < cols; left_edge++) {

vector<int> rectangle_in_between (rows, 0);

for (int right_edge = left_edge; right_edge < cols; right_edge++) {

for (int r = 0; r < rows; r++) {
rectangle_in_between[r] += matrix[r][right_edge];
}
maxsum = max ( maxsum, Kadanes_MaxSum (rectangle_in_between) );
}
}
cout << "Maximum sum in subrectangle: " << maxsum << endl;
}

int main() {

vector<vector<int>> matrix1 = {{  1, -2, -6, 0 },
{  9,  3, -5, 3 },
{ -5,  1, -4, 1 },
{ -3,  7,  0,-3 },
};
GetMaxSumRectangle(matrix1);

vector<vector<int>> matrix2 = {{ 8, -2, -6, 11 },
{ 9, -4, -5, -3 },
{-5, -16, 14,-1 },
{-3, -7, -1, 13 },
};
GetMaxSumRectangle(matrix2);
return 0;
};
``````

Output

``````Maximum sum in sub-rectangle: 12
Maximum sum in sub-rectangle: 25
``````