Algotree > Algorithms > Dynamic Programming > Finding maximum sum subrectangle > Finding maximum sum subrectangle using aggregate rectangles

Finding maximum sum subrectangle using aggregate rectangles

Finding the maximum sum subrectangle in a two dimensional array/matrix.

A brute-force way of finding the maximum sum sub-rectangle is to set the postion of the top-left and bottom-right corners of the sub-rectangle and adding the integers within it while iterating through all the rows sequentially. Setting all the top-left and bottom-right corners of the sub-rectangles within a given rectangle takes O ( n^4 ) time, adding the elements within it takes O ( n^2 ) time. Thus the simplistic brute-force algorithm takes O ( n^6 ) time.

A better ( not the best ) approach than the above is shown below that has the time complexity of O ( n^4 ).

Dynamic programming approach of finding the maximum sum sub-rectangle

Convert the given rectangle into an aggregate rectangle. In an aggregate rectangle, each integer at position r (row) and c (column) indicates the sum of a sub-rectangle whose top-left corner is ( 0, 0 ) and bottom-right corner is ( r, c ).
The aggregate rectangle can be calculated in O ( n ^ 2 ) time and is based on the inclusion-exclusion principal.

Inclusion-Exclusion principle
1. For each row r in ROWS :
2.      For each column c in COLS :
3.          If r > 0 ( Add integers from the row above ) :
                rectangle [ r ] [ c ] += rectangle [ r - 1 ] [ c ]
4.          If c > 0 ( Add integers from the column to the left ) :
                rectangle [ r ] [ c ] += rectangle [ r ] [ c - 1 ]
5.          If r > 0 and c > 0
                ( Subtract the integer at the diagonal position that got added twice during the previous row and column additions ) :
                rectangle [ r ] [ c ] -= rectangle [ r - 1 ] [ c - 1 ]

Once an aggregate rectangle as shown below is obtained, finding the maximum sum subrectangle can be done in O ( n^4 ).

Maxsum_Subrectangle

All possible subrectangles can be obtained by setting the position of the top-left and bottom-right corner(s). The sum of the subrectangle thus formed can be deduced by using the inclusion-exclusion principle.

Example of finding the sum of a subrectangle with co-ordinates : Top-Left ( 2, 2 ) and Bottom-Right ( 3, 3 )
Left is 2 and 2 > 0 : sum of subrectangle = 2 - (-20) = 22 ( subtract the aggregate rectangle on the left )
Top is 2 and 2 > 0 : sum of subrectangle = 22 - 8 = 14 ( subtract the aggregate rectangle above )
Left and Top both are greater than 0 : sum of rectangle = 14 + 11 = 25 ( add the aggregate rectangle in the diagonal location above as it got subtracted twice )

Time complexity of finding the maximum sum subrectangle : O ( n^4 ). If the length is ‘l’ and the breadth is ‘b’ then the time complexity is O ( l^2 . b^2 ) which is effectively O( n^4 ) if l equals b equals n.

The time complexity of finding the maximum sum subrectangle can be further reduced to O ( n^3 ) using dynamic programming with Kadane’s algorithm.

C++ : Maximum Sum SubRectangle implementation using Dynamic Programming in C++11

#include<iostream>
#include<vector>

using namespace std;

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

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

    // Inclusion Exclusion Principle
    for(int r=0; r<rows; r++){
        for(int c=0; c<cols; c++){

            // Add element from the previous column
            if(r > 0) 
               matrix[r][c] += matrix[r-1][c];    
            // Add element from the previous row
            if(c > 0) 
               matrix[r][c] += matrix[r][c-1];
            // Subtract diagonal element that got added twice from previous row and column additions
            if(r > 0 && c > 0) 
               matrix[r][c] -= matrix[r-1][c-1];
         }
    }   

    int maxsum = -127*100*100;

    // Co-ordinates of maximum sum sub rectangle
    int from_row, from_column;
    int to_row, to_column;

    for(int i=0; i<rows; i++) for(int j=0; j<cols; j++)
        for(int k=i; k<rows; k++) for(int l=j; l<cols; l++) { 

            int sum_subrectangle = matrix[k][l];

            if(i > 0)  
               sum_subrectangle -= matrix[i-1][l];
            if(j > 0)  
               sum_subrectangle -= matrix[k][j-1];
            if(i > 0 && j > 0)  
               sum_subrectangle += matrix[i-1][j-1];

            if(sum_subrectangle > maxsum){
               from_row = i, from_column = j, to_row = k, to_column = l;
               maxsum = sum_subrectangle;
            }
        }

    cout << "Maximum sum in sub-rectangle: " << maxsum << endl;
    cout << "Maximum sum rectangle co-ordinates: (" << from_row << "," << from_column << ")" << "-" << "(" << to_row << "," << to_column << ")" << 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 rectangle co-ordinates: (1,0)-(1,1)
Maximum sum in sub-rectangle: 25
Maximum sum rectangle co-ordinates: (2,2)-(3,3)

Python : Maximum Sum SubRectangle implementation using Dynamic Programming in Python3

#!/usr/bin/python3

def GetMaxSumRectangle(matrix):

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

    # Inclusion Exclusion Principle
    for r in range(rows):
        for c in range(cols):

            # Add element from the previous column
            if(r > 0): 
               matrix[r][c] += matrix[r-1][c]

            # Add element from the previous row
            if(c > 0): 
               matrix[r][c] += matrix[r][c-1]

            # Subtract diagonal element that got added twice from previous row and column additions
            if(r > 0 and c > 0): 
               matrix[r][c] -= matrix[r-1][c-1]

    maxsum = -100*100*100

    for i in range(rows):
        for j in range(cols):
            for k in range(i, rows):
                for l in range(j, cols):

                    sum_subrectangle = matrix[k][l]

                    if(i > 0): 
                       sum_subrectangle -= matrix[i-1][l]
                    if(j > 0): 
                       sum_subrectangle -= matrix[k][j-1]
                    if(i > 0 and j > 0): 
                       sum_subrectangle += matrix[i-1][j-1]

                    if(sum_subrectangle > maxsum):
                       # Co-ordinates of maximum sum sub rectangle
                       from_row = i 
                       from_column = j 
                       to_row = k 
                       to_column = l 
                       maxsum = sum_subrectangle

    print("Maximum sum in sub-rectangle: "+str(maxsum))
    print("Maximum sum rectangle co-ordinates: (" + str(from_row) + "," + str(from_column) + ")" + "-" + "(" + str(to_row) + "," + str(to_column) + ")")

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 rectangle co-ordinates: (1,0)-(1,1)
Maximum sum in sub-rectangle: 25
Maximum sum rectangle co-ordinates: (2,2)-(3,3)