Given a 2D matrix, finds the submatrix with the largest sum of its elements. Uses Kadane's algorithm to speed up process.

KadaneMatrix.py

############################################################################################
#   Max Sum Rectangle (2D Kadane Algorithm)
#   Finds the submatrix with the largest sum of its values using Kadane's algorithm
#   
#   
#   
############################################################################################
def Kadane(arr):
    #Keep track of sums
    current_sum = arr[0]
    max_sum = arr[0]
    
    #Keep track of position in array
    left, right = 0, 0
    mleft, mright = 0, 0

    #Iterate through array w/ Kadane's algorithm
    #would normally use max(current_sum, max_sum)
    #but using if instead to keep track of positions
    for i in range(1, len(arr)):
        current_sum += arr[i]
        right = i
        if current_sum < arr[i]:
            current_sum = arr[i]
            left = i
        if max_sum < current_sum:
            max_sum = current_sum
            mleft, mright = left, right
            
    return max_sum, mleft, mright

def MaxSumRect(matrix):
    #Initialize values to iterate through matrix & keep track of sums
    col = len(matrix[0])
    rows = len(matrix)
    maxVal = 0
    RunningSum = [0 for i in range(rows)] #Records sum of each row

    mLeft, mRight, mTop, mBot = 0, 0, 0, 0 #Keep track of corners in submatrix w/ max sum

    #Iterate through matrix while using Kadane's algorithm on each iteration
    #Left side starts at 0 while right side iterates from 0 to last column
    #each time using Kadane to update max sum value. Then left side moves to
    #1 and iterate right side from 1 to last column. Keep doing this until
    #left side equals right side i.e. both are in last column
    for left in range(col): #Left Corner
        for right in range(left, col): #Right Corner
            for i in range(rows):
                RunningSum[i] += matrix[i][right]

            #Use Kadane's algorithm to find largest consecutive sum
            temp, top, bot= Kadane(RunningSum)    
            
            #If new max sum is found, update corners and max value
            if maxVal < temp:
                mLeft, mRight = left, right
                mTop, mBot = top, bot
                maxVal = temp    
        RunningSum = [0 for i in range(rows)] #Reset running sum to prevent overlap

    #Recover submatrix with max sum
    solMat = []
    for i in range(mTop, mBot+1): #Top to bottom
        tempMat = matrix[i][mLeft:mRight+1] #Left to right
        solMat.append(tempMat)
    
    return solMat

#Print Matrix
def printMat(matrix):
    for i in matrix:
        print(i)
    print(" ")

m = [ [6, -5, -7, 4, -4],
      [-9, 3, -6, 5, 2],
      [-10, 4, 7, -6, 3],
      [-8, 9, -3, 3, -7]
    ]

printMat(m)
ans = MaxSumRect(m)
printMat(ans)