Algotree > Algorithms > Dynamic Programming > Finding maximum sum subrectangle > Maximum sum subrectangle using Kadane's algorithm

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 Kadane_Max_Sum_Subrectangle

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

Time complexity : O ( n³ ).

Kadane’s algorithm implementation

#!/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 Kadanes_MaxSum (vector<int>& vec) {

    int sum = vec[0]; // Sum found till current element
    int max_sum = sum;
    
    for(int i=1; i<vec.size(); i++) {
        if (sum + vec[i] > vec[i]) {
            sum = sum + vec[i];
        } else {
            sum = vec[i];
        }
        max_sum = max(sum, max_sum);
    }
    return max_sum;
}

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