Finding the maximum sum subrectangle using dynamic programming with Kadane's algorithm

Finding the maximum sum subrectangle in a two dimensional array / matrix using dynamic programming with Kadane’s algorithm

The idea behind this approach is quite simple and is described below.

  • Get hold of all the subrectangles by iterating through the left most column to the right most column.
  • For every subrectangle get the rows summations and find the maximum sum of the subarray within it by using Kadane’s algorithm

Kadane_Max_Sum_Subrectangle

Time complexity : O ( n3 )



Kadane’s algorithm implementation

#!/usr/bin/python3

def Maxsum_Kadanes (array):

      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):

    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 Kadanes_MaxSum (vector<int> array) {

      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



Copyright (c) 2019-2021, Algotree.org.
All rights reserved.