maxSumSubArray2D.py

"""
Dynamic Programming | Set 27 (Maximum sum rectangle in a 2D matrix)
http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/

The idea is that to rotate the matrix and use kadane's maxSumArray and
add the lists one by one to get the maximum sum of the matrix
"""

import sys
def maxSumSubArray(arr):
    # Base case
    max_ending_here = max_so_far = 0
    for x in arr:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far


def findMaxSum(matrix):
    currentSum, maxSum, Sum, maxLeft, maxRight, maxUp, maxDown = 0,0,0,0,0,0,0
    rotateMatrix = zip(*matrix)[::-1]
    rotatedMatrix = [[j for j in i] for i in rotateMatrix]
    r = len(rotatedMatrix[0])
    c = len(rotatedMatrix)
    newList = [0]*len(matrix)
    for i in range(r):
        for j in range(i,r):
            newList = sumTwoLists(newList,rotatedMatrix[j])
            maxSum = max(maxSum, maxSumSubArray(newList)) 
        newList = [0]*len(matrix)
    return maxSum        
           

def sumTwoLists(a, b):
    return [x+y for x,y in zip(a, b)]      
    
    
matrix =  [[2,  1, -3, -4,  5],[ 0,  6,  3,  4,  1],[ 2, -2, -1,  4, -5],[-3,  3,  1,  0,  3]]   
findMaxSum(matrix)