Easy Python3 O(n*m) sol using matrix prefix sum and Submatrix sum query


#1
class Solution:
# @param A : list of list of integers
# @param B : integer
# @return an integer
def solve(self, a, k):
    maxsum=float('-inf')
    currsum=0
    for i in range(len(a)):
        for j in range(len(a[0])):
            if i==j==0:
                a[i][j]=a[i][j]
            elif i==0 and j>0:
                a[i][j]+=a[i][j-1]
            elif i>0 and j==0:
                a[i][j]+=a[i-1][j]
            else:
                a[i][j]+=a[i - 1][j]+a[i][j - 1] -a[i - 1][j - 1]
    for i in range(len(a)):
        for j in range(len(a[0])):
            currsum=a[i][j]
            if i<k-1 and j<k-1:
                continue
            if i-k>=0:
                currsum-=a[i-k][j]
            if j-k>=0:
                currsum-=a[i][j-k]
            if i-k>=0 and j-k>=0:
                currsum+=a[i-k][j-k]
            if i>=k-1 and j>=k-1:
                if currsum>maxsum:
                    maxsum=currsum
    return maxsum