M02766: 最大子矩阵

matrices, kadane, http://cs101.openjudge.cn/pctbook/M02766/

已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。

比如，如下4 * 4的矩阵

0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2

的最大子矩阵是

9 2 -4 1 -1 8

这个子矩阵的大小是15。

输入

输入是一个N * N的矩阵。输入的第一行给出N (0 < N <= 100)。再后面的若干行中，依次（首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数……）给出矩阵中的N2个整数，整数之间由空白字符分隔（空格或者空行）。已知矩阵中整数的范围都在[-127, 127]。

输出

输出最大子矩阵的大小。

样例输入

4
0 -2 -7 0 9 2 -6 2
-4 1 -4  1 -1

8  0 -2

样例输出

来源：翻译自 Greater New York 2001 的试题

python

def kadane(s):
    curr_max = total_max = s[0]
    for x in s[1:]:
        curr_max = max(x, curr_max + x)
        total_max = max(total_max, curr_max)
    return total_max

def max_sum_matrix(mat):
    max_sum = -float('inf')
    row, col = len(mat), len(mat[0])
    for top in range(row):
        col_sum = [0] * col
        for bottom in range(top, row):
            for c in range(col):
                col_sum[c] += mat[bottom][c]
            max_sum = max(max_sum, kadane(col_sum))
    return max_sum

n = int(input())
nums = []
while len(nums) < n**2:
    nums.extend(input().split())
mat = [list(map(int, nums[i*n:(i+1)*n])) for i in range(n)]
print(max_sum_matrix(mat))

一、算法原理
二维最大子矩阵问题，可以通过「行压缩 + 一维 Kadane」解决。
思想：
固定子矩阵的上边界 top
固定子矩阵的下边界 bottom
对每一列求“从 top 到 bottom 行的列和”
得到一个一维数组 col_sum
对 col_sum 使用 Kadane 算法，求最大子数组和（相当于固定上下边界后，在列方向找到左右边界）
举例：
0 -2 -7 0
9  2 -6 2
-4 1 -4 1
-1 8  0 -2
比如 top=1, bottom=3，则 col_sum = [9-4-1, 2+1+8, -6-4+0, 2+1-2] = [4, 11, -10, 1] → Kadane(col_sum) = 15，对应矩阵正是样例输出。
二、核心代码结构分析
python
def kadane(s):
    curr_max = total_max = s[0]
    for x in s[1:]:
        curr_max = max(x, curr_max + x)
        total_max = max(total_max, curr_max)
    return total_max
一维 Kadane：
curr_max 表示“以当前元素结尾的最大连续和”；
total_max 表示“全局最大和”。
python
def max_sum_matrix(mat):
    max_sum = -float('inf')
    row, col = len(mat), len(mat[0])
    for top in range(row):
        col_sum = [0] * col
        for bottom in range(top, row):
            for c in range(col):
                col_sum[c] += mat[bottom][c]
            max_sum = max(max_sum, kadane(col_sum))
    return max_sum
外层 top 和 bottom 控制上下边界（O(n²)）；内层 Kadane 处理列方向（O(n)）；整体时间复杂度 O(n³)，适用于 N ≤ 100 的题目。
三、输入处理逻辑说明
OJ 给的输入可能有空格和换行混合，所以正确做法是——
不要逐行严格读取，而是一直读取直到获取 N² 个整数。
python
n = int(input())
nums = []
while len(nums) < n**2:
    nums.extend(input().split())
mat = [list(map(int, nums[i*n:(i+1)*n])) for i in range(n)]
print(max_sum_matrix(mat))
四、扩展思考（可选优化）
前缀和加速列和计算
可以预先构建行方向前缀和 prefix[r][c]
使得 col_sum[c] = prefix[bottom][c] - prefix[top-1][c]
时间复杂度仍然 O(n³)，但常数项更小。
全负数矩阵
Kadane 已正确处理（返回最大单个元素）。
空间复杂度
O(n)，仅用到 col_sum。

这个问题是一个经典的“最大子矩阵和”问题，属于二维动态规划的应用场景。解决的核心思想是将二维问题降为多个一维的“最大子段和”问题（Kadane 算法），从而降低复杂度。

✅ 解题思路（二维 Kadane 变种）

固定两个行索引 top 和 bottom，将这两行之间（包含）的矩阵压缩成一个一维数组 temp_col_sum，其中每个元素是这几行中该列的和。
在这个一维数组上应用“最大子段和”算法（Kadane）求出最大和。
枚举所有可能的 top 和 bottom 组合，更新全局最大值。

✅ 代码实现（Python）

python

'''
为了找到最大的非空子矩阵，可以使用动态规划中的Kadane算法进行扩展来处理二维矩阵。
基本思路是将二维问题转化为一维问题：可以计算出从第i行到第j行的列的累计和，
这样就得到了一个一维数组。然后对这个一维数组应用Kadane算法，找到最大的子数组和。
通过遍历所有可能的行组合，我们可以找到最大的子矩阵。
'''
def max_submatrix(matrix, n):
    def kadane(arr):
      	# max_ending_here 用于追踪到当前元素为止包含当前元素的最大子数组和。
        # max_so_far 用于存储迄今为止遇到的最大子数组和。
        max_end_here = max_so_far = arr[0]
        for x in arr[1:]:
          	# 对于每个新元素，我们决定是开始一个新的子数组（仅包含当前元素 x），
            # 还是将当前元素添加到现有的子数组中。这一步是 Kadane 算法的核心。
            max_end_here = max(x, max_end_here + x)
            max_so_far = max(max_so_far, max_end_here)
        return max_so_far

    max_sum = float('-inf')

    for top in range(n):
        temp_col_num = [0] * n
        for bottom in range(top, n):
            for col in range(n):
                temp_col_num[col] += matrix[bottom][col]
            max_sum = max(max_sum, kadane(temp_col_num))
    return max_sum

# 输入处理
import sys
data = sys.stdin.read().split()
n = int(data[0])
numbers = list(map(int, data[1:]))
matrix = [numbers[i * n:(i + 1) * n] for i in range(n)]

max_sum = max_submatrix(matrix, n)
print(max_sum)

✅ 时间复杂度分析

外层双重循环（top 和 bottom）：O(n²)
内层 Kadane：O(n)
总体时间复杂度：O(n³)，对于 n <= 100 是可接受的。

M02766: 最大子矩阵 ​

思想： ​

举例： ​

M02766: 最大子矩阵

思想：

举例：