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's Maximum Sum SubRectangle

The time complexity of finding the maximum sum subrectangle using Kadane’s algorithm : O ( n^3 )


C++ : Implementation of Maximum Sum SubRectangle using Dynamic Programming with Kadane's algorithm in C++11

Python : Implementation of Maximum Sum SubRectangle using Dynamic Programming with Kadane’s algorithm in Python3

#!/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

Copyright © 2019, Algotree.org.
All rights reserved.