这个解决方案首先计算了矩阵的行和列前缀和，以便快速计算任何子矩阵的行和列的和。然后，它尝试找到最大的幻方，从最大可能的边长开始，逐步减小边长，直到找到一个有效的幻方或者边长降到1。对于每个可能的边长，它会遍历所有可能的起始点，检查是否所有行、列以及对角线的和都等于第一行的和。如果找到这样的幻方，则立即返回这个边长。如果没有找到，最后返回1（因为任何1x1的子矩阵都是幻方）。
时间复杂度: O(mn + min(m, n)^3)
空间复杂度: O(mn)
class Solution:
def largestMagicSquare(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
# Calculate row prefix sums
rowsum = [[0] * n for _ in range(m)]
for i in range(m):
rowsum[i][0] = grid[i][0]
for j in range(1, n):
rowsum[i][j] = rowsum[i][j - 1] + grid[i][j]
# Calculate column prefix sums
colsum = [[0] * n for _ in range(m)]
for j in range(n):
colsum[0][j] = grid[0][j]
for i in range(1, m):
colsum[i][j] = colsum[i - 1][j] + grid[i][j]
# Check all possible sizes of magic squares from largest to smallest
for edge in range(min(m, n), 1, -1):
for i in range(m - edge + 1):
for j in range(n - edge + 1):
# Check if all rows have the same sum
stdsum = rowsum[i][j + edge - 1] - (0 if j == 0 else rowsum[i][j - 1])
check = True
for ii in range(i + 1, i + edge):
if rowsum[ii][j + edge - 1] - (0 if j == 0 else rowsum[ii][j - 1]) != stdsum:
check = False
break
if not check:
continue
# Check if all columns have the same sum
for jj in range(j, j + edge):
if colsum[i + edge - 1][jj] - (0 if i == 0 else colsum[i - 1][jj]) != stdsum:
check = False
break
if not check:
continue
# Calculate the sums of both diagonals
d1 = d2 = 0
for k in range(edge):
d1 += grid[i + k][j + k]
d2 += grid[i + k][j + edge - 1 - k]
if d1 == stdsum and d2 == stdsum:
return edge
return 1
