Maximum sum submatrix | Python3 program for the above approach ; Function to find maximum continuous maximum sum in the array ; Stores current and maximum sum ; Traverse the array v ; Add the value of the current element ; Update the maximum sum ; Return the maximum sum ; Function to find the maximum submatrix sum ; Store the rows and columns of the matrix ; Create an auxiliary matrix Traverse the matrix , prefix and initialize it will all 0 s ; Calculate prefix sum of all rows of matrix A [ ] [ ] and store in matrix prefix [ ] ; Update the prefix [ ] [ ] ; Store the maximum submatrix sum ; Iterate for starting column ; Iterate for last column ; To store current array elements ; Traverse every row ; Store the sum of the kth row ; Update the prefix sum ; Push it in a vector ; Update the maximum overall sum ; Print the answer ; Driver Code ; Function Call
import sys NEW_LINE def kadane ( v ) : NEW_LINE INDENT currSum = 0 NEW_LINE maxSum = - sys . maxsize - 1 NEW_LINE for i in range ( len ( v ) ) : NEW_LINE INDENT currSum += v [ i ] NEW_LINE if ( currSum > maxSum ) : NEW_LINE INDENT maxSum = currSum NEW_LINE DEDENT if ( currSum < 0 ) : NEW_LINE INDENT currSum = 0 NEW_LINE DEDENT DEDENT return maxSum NEW_LINE DEDENT def maxSubmatrixSum ( A ) : NEW_LINE INDENT r = len ( A ) NEW_LINE c = len ( A [ 0 ] ) NEW_LINE prefix = [ [ 0 for i in range ( c ) ] for j in range ( r ) ] NEW_LINE for i in range ( r ) : NEW_LINE INDENT for j in range ( c ) : NEW_LINE INDENT if ( j == 0 ) : NEW_LINE INDENT prefix [ i ] [ j ] = A [ i ] [ j ] NEW_LINE DEDENT else : NEW_LINE INDENT prefix [ i ] [ j ] = A [ i ] [ j ] + prefix [ i ] [ j - 1 ] NEW_LINE DEDENT DEDENT DEDENT maxSum = - sys . maxsize - 1 NEW_LINE for i in range ( c ) : NEW_LINE INDENT for j in range ( i , c ) : NEW_LINE INDENT v = [ ] NEW_LINE for k in range ( r ) : NEW_LINE INDENT el = 0 NEW_LINE if ( i == 0 ) : NEW_LINE INDENT el = prefix [ k ] [ j ] NEW_LINE DEDENT else : NEW_LINE INDENT el = prefix [ k ] [ j ] - prefix [ k ] [ i - 1 ] NEW_LINE DEDENT v . append ( el ) NEW_LINE DEDENT maxSum = max ( maxSum , kadane ( v ) ) NEW_LINE DEDENT DEDENT print ( maxSum ) NEW_LINE DEDENT matrix = [ [ 0 , - 2 , - 7 , 0 ] , [ 9 , 2 , - 6 , 2 ] , [ - 4 , 1 , - 4 , 1 ] , [ - 1 , 8 , 0 , - 2 ] ] NEW_LINE maxSubmatrixSum ( matrix ) NEW_LINE