算法1
(暴力枚举) $O(n^4)$
Python 代码
N = int(input())
metrix = [[0]*N for _ in range(N)]
row, col = 0, 0
while row < N and col < N:
str = input()
if str == '': continue
nums = list(map(int, str.split()))
for num in nums:
metrix[row][col] = num
col += 1
if col == N:
col = 0
row += 1
s = [[0] * (N+1) for _ in range(N+1)]
for i in range(1, N+1):
for j in range(1, N+1):
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + metrix[i-1][j-1]
res = -float('inf')
for l_x in range(0, N): # 宽度为0-N-1
for l_y in range(0, N):
for x in range(1, N+1-l_x):
for y in range(1, N+1-l_y):
xb, yb = x + l_x, y + l_y
res = max(res, s[xb][yb] - s[xb][y-1] - s[x-1][yb] + s[x-1][y-1])
print(res)
算法2
(贪心) $O(n^3)$
Python 代码
N = int(input())
metrix = [[0]*N for _ in range(N)]
row, col = 0, 0
while row < N and col < N:
str = input()
if str == '': continue
nums = list(map(int, str.split()))
for num in nums:
metrix[row][col] = num
col += 1
if col == N:
col = 0
row += 1
s = [[0] * (N+1) for _ in range(N+1)]
for i in range(1, N+1):
for j in range(1, N+1):
s[i][j] = s[i-1][j] + metrix[i-1][j-1] # 前缀和
res = -float('inf')
for top in range(1, N+1):
for bot in range(top, N+1):
sum = 0
for col in range(1, N+1):
sum = max(sum, 0) + s[bot][col] - s[top-1][col]
res = max(sum, res)
print(res)