Envío 4794

Código

import math

def smsum(mat):
    N, M = len(mat), len(mat[0])
    for r in range(1, N):    
        mat[r][0] += mat[r - 1][0]         
    for c in range(1, M):    
        mat[0][c] += mat[0][c - 1]         
    for r in range(1, N):    
        for c in range(1, M):     
            mat[r][c] += mat[r - 1][c]     
            mat[r][c] += mat[r][c - 1]
            mat[r][c] -= mat[r - 1][c - 1]

def query(m, r1, c1, r2, c2):
    if r1 == c1 == 0:
        return m[r2][c2]
    if r1 == 0:
        return m[r2][c2] - m[r2][c1 - 1]
    if c1 == 0:
        return m[r2][c2] - m[r1 - 1][c2]
    return m[r2][c2] - m[r1 - 1][c2] - m[r2][c1 - 1] + m[r1 - 1][c1 - 1]

def max_submatrix(m):
    smsum(m)
    N, M = len(m), len(m[0])
    mx = -math.inf
    for r in range(N):
        for c in range(M):
            for rr in range(r, N):
                for cc in range(c, M):
                    mx = max(mx, query(m, r, c, rr, cc))
    return mx    

if __name__ == "__main__":
    N, M = map(int, input().split(" "))
    mat = []
    for _ in range(N):
        row = map(int, input().split(" "))
        mat.append(list(row))
    print(max_submatrix(mat))