# your code goes here
'''def kadane(v):
# Stores current and maximum sum
currSum = 0
maxSum = -sys.maxsize - 1
# Traverse the array v
for i in range(len(v)):
# Add the value of the
# current element
currSum += v[i]
# Update the maximum sum
if (currSum > maxSum):
maxSum = currSum
if (currSum < 0):
currSum = 0
# Return the maximum sum
return maxSum
# Function to find the maximum
# submatrix sum'''
def maxSubmatrixSum(A):
r = len(A)
c = len(A[0])
prefix = [[0 for i in range(c)]
for j in range(r)]
# Calculate prefix sum of all
# rows of matrix A[][] and
# store in matrix prefix[]
for i in range(r):
for j in range(c):
# Update the prefix[][]
if (j == 0):
prefix[i][j] = A[i][j]
else:
prefix[i][j] = A[i][j] + prefix[i][j - 1]
maxSum = -9999999999
''' for i in range(c):
# Iterate for last column
for j in range(i, c):
# To store current array
# elements
v = []
# Traverse every row
for k in range(r):
# Store the sum of the
# kth row
el = 0
# Update the prefix
# sum
if (i == 0):
el = prefix[k][j]
else:
el = prefix[k][j] - prefix[k][i - 1]
# Push it in a vector
v.append(el)
# Update the maximum
# overall sum
maxSum = max(maxSum, kadane(v))
# Print the answer
print(maxSum)'''
# Driver Code
matrix = [ [ 0, -2, -7, 0 ],
[ 9, 2, -6, 2 ],
[ -4, 1, -4, 1 ],
[ -1, 8, 0, -2 ] ]
# Function Call
maxSubmatrixSum(matrix)
IyB5b3VyIGNvZGUgZ29lcyBoZXJlCicnJ2RlZiBrYWRhbmUodik6CiAgICAgCiAgICAjIFN0b3JlcyBjdXJyZW50IGFuZCBtYXhpbXVtIHN1bQogICAgY3VyclN1bSA9IDAKICAgICAKICAgIG1heFN1bSA9IC1zeXMubWF4c2l6ZSAtIDEKICAgICAKICAgICMgVHJhdmVyc2UgdGhlIGFycmF5IHYKICAgIGZvciBpIGluIHJhbmdlKGxlbih2KSk6CiAgICAgICAgIAogICAgICAgICMgQWRkIHRoZSB2YWx1ZSBvZiB0aGUKICAgICAgICAjIGN1cnJlbnQgZWxlbWVudAogICAgICAgIGN1cnJTdW0gKz0gdltpXQogICAgICAgICAKICAgICAgICAjIFVwZGF0ZSB0aGUgbWF4aW11bSBzdW0KICAgICAgICBpZiAoY3VyclN1bSA+IG1heFN1bSk6CiAgICAgICAgICAgIG1heFN1bSA9IGN1cnJTdW0KICAgICAgICBpZiAoY3VyclN1bSA8IDApOgogICAgICAgICAgICBjdXJyU3VtID0gMAogICAgIAogICAgIyBSZXR1cm4gdGhlIG1heGltdW0gc3VtCiAgICByZXR1cm4gbWF4U3VtCiAKIyBGdW5jdGlvbiB0byBmaW5kIHRoZSBtYXhpbXVtCiMgc3VibWF0cml4IHN1bScnJwpkZWYgbWF4U3VibWF0cml4U3VtKEEpOgogICAgIAogICAKICAgIHIgPSBsZW4oQSkKICAgIGMgPSBsZW4oQVswXSkKICAgICAKICAgIHByZWZpeCA9IFtbMCBmb3IgaSBpbiByYW5nZShjKV0KICAgICAgICAgICAgICAgICBmb3IgaiBpbiByYW5nZShyKV0KICAgICAKICAgICMgQ2FsY3VsYXRlIHByZWZpeCBzdW0gb2YgYWxsCiAgICAjIHJvd3Mgb2YgbWF0cml4IEFbXVtdIGFuZAogICAgIyBzdG9yZSBpbiBtYXRyaXggcHJlZml4W10KICAgIGZvciBpIGluIHJhbmdlKHIpOgogICAgICAgIGZvciBqIGluIHJhbmdlKGMpOgogICAgICAgICAgICAgCiAgICAgICAgICAgICMgVXBkYXRlIHRoZSBwcmVmaXhbXVtdCiAgICAgICAgICAgIGlmIChqID09IDApOgogICAgICAgICAgICAgICAgcHJlZml4W2ldW2pdID0gQVtpXVtqXQogICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgcHJlZml4W2ldW2pdID0gQVtpXVtqXSArIHByZWZpeFtpXVtqIC0gMV0KICAgICAKICAgIAogICAgbWF4U3VtID0gLTk5OTk5OTk5OTkKICAgICAKICAgIAogICAgJycnIGZvciBpIGluIHJhbmdlKGMpOgogICAgICAgICAKICAgICAgICAjIEl0ZXJhdGUgZm9yIGxhc3QgY29sdW1uCiAgICAgICAgZm9yIGogaW4gcmFuZ2UoaSwgYyk6CiAgICAgICAgICAgICAKICAgICAgICAgICAgIyBUbyBzdG9yZSBjdXJyZW50IGFycmF5CiAgICAgICAgICAgICMgZWxlbWVudHMKICAgICAgICAgICAgdiA9IFtdCiAgICAgICAgICAgICAKICAgICAgICAgICAgIyBUcmF2ZXJzZSBldmVyeSByb3cKICAgICAgICAgICAgZm9yIGsgaW4gcmFuZ2Uocik6CiAgICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgICAjIFN0b3JlIHRoZSBzdW0gb2YgdGhlCiAgICAgICAgICAgICAgICAjIGt0aCByb3cKICAgICAgICAgICAgICAgIGVsID0gMAogICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgIyBVcGRhdGUgdGhlIHByZWZpeAogICAgICAgICAgICAgICAgIyBzdW0KICAgICAgICAgICAgICAgIGlmIChpID09IDApOgogICAgICAgICAgICAgICAgICAgIGVsID0gcHJlZml4W2tdW2pdCiAgICAgICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgICAgIGVsID0gcHJlZml4W2tdW2pdIC0gcHJlZml4W2tdW2kgLSAxXQogICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgIyBQdXNoIGl0IGluIGEgdmVjdG9yCiAgICAgICAgICAgICAgICB2LmFwcGVuZChlbCkKICAgICAgICAgICAgIAogICAgICAgICAgICAjIFVwZGF0ZSB0aGUgbWF4aW11bQogICAgICAgICAgICAjIG92ZXJhbGwgc3VtCiAgICAgICAgICAgIG1heFN1bSA9IG1heChtYXhTdW0sIGthZGFuZSh2KSkKICAgICAKICAgICMgUHJpbnQgdGhlIGFuc3dlcgogICAgcHJpbnQobWF4U3VtKScnJwogCiMgRHJpdmVyIENvZGUKbWF0cml4ID0gWyBbIDAsIC0yLCAtNywgMCBdLAogICAgICAgICAgIFsgOSwgMiwgLTYsIDIgXSwKICAgICAgICAgICBbIC00LCAxLCAtNCwgMSBdLAogICAgICAgICAgIFsgLTEsIDgsIDAsIC0yIF0gXQogICAgICAgICAgICAKIyBGdW5jdGlvbiBDYWxsCm1heFN1Ym1hdHJpeFN1bShtYXRyaXgp