Python Solution : O(n^2)


#1

def kingdomWar(A):
row = len(A)
col = len(A[0])
t = [0]*row
for i in range(row):
t[i] = [0]*col
maxVal = -2**32
for i in range(row-1,-1,-1):
for j in range(col-1,-1,-1):
if i == row-1 and j == col-1:
t[i][j] = A[i][j]
elif i == row-1:
t[i][j] = t[i][j+1]+A[i][j]
elif j == col-1:
t[i][j] = t[i+1][j]+A[i][j]
else:
t[i][j] = t[i+1][j]+t[i][j+1]+A[i][j]-t[i+1][j+1]
maxVal = max(maxVal,t[i][j])
return maxVal
class Solution:
# @param A : list of list of integers
# @return an integer
def solve(self, A):
return kingdomWar(A)