Maximum Sub Array Sum 2 Dimensional

In this class, We discuss Maximum Sub Array Sum 2 Dimensional.

The reader should have prior knowledge of kadane’s algorithm. Click Here.

For Complete YouTube Video: Click Here

The below diagram shows the two-dimensional array.

The orange box is the sub-array with the maximum sum.

The sum of all the elements in the sub-array should be maximum.

We can take a single element as sub array.

We can take all the elements as sub array.

Adding all the elements in the orange box, we get the value 29.

In kadane’s algorithm, we identified the maximum sub-array sum in a single-dimensional array.

The same algorithm finds the sub-array sum in two dimensional.

Procedure:

Take the first line in the array and apply kadane’s algorithm.

The first line will return the maximum sum of 3.

Take the first two lines, add the elements in each column, and make it a single-dimensional array.

Again apply kadane’s algorithm on the newly formed single-dimensional array.

Similarly, Take all the combinations of lines and add the elements and apply kadane’s algorithm.

The combination which gives the maximum sum is the required output.

The complete explanation is in the video link provided above.

Code:

class Solution:
    def kadanes(self,arr, n):
        s, maxi = arr[0], arr[0]
        for i in range(1,n):
            s += arr[i]
            s = max(s,arr[i])
            maxi = max(s,maxi)
        return maxi
       
       
    def maximumSumRectangle(self,R,C,M):
        res = M[0][0]
        for starti in range(R):
            subMatSum = [0 for _ in range(C)]
            for i in range(starti, R):
                for j in range(C):
                    subMatSum[j] += M[i][j]
                res = max(res, self.kadanes(subMatSum, C))
        return res
N = int(input(“enter number of rows”))
M = int(input(“enter number of columns”))
a=[]
for i in range(N):
    s=[]
    for j in range(M):
        x=int(input())
        s.append(x)
    a.append(s)
ob = Solution()
print(ob.maximumSumRectangle(N,M,a))