题解 | 最大子矩阵

def max_submatrix_sum(matrix):
    n = len(matrix)
    max_sum = float("-inf")

    # 遍历所有可能的行组合
    for i in range(n):
        temp = [0] * n  # 临时数组，存储从第 i 行到第 j 行的列累加和
        for j in range(i, n):
            # 更新临时数组
            for k in range(n):
                temp[k] += matrix[j][k]
            # 对临时数组使用 Kadane 算法，找到最大子数组和
            current_max = temp[0]
            global_max = temp[0]
            for k in range(1, n):
                current_max = max(temp[k], current_max + temp[k])
                global_max = max(global_max, current_max)
            # 更新全局最大值
            max_sum = max(max_sum, global_max)

    return max_sum


# 输入处理
n = int(input())
matrix = []
for _ in range(n):
    row = list(map(int, input().split()))
    matrix.append(row)

# 计算最大子矩阵和
result = max_submatrix_sum(matrix)
print(result)