给定约束条件的矩阵最大和问题

1. 问题描述

给定一个 m x n 的整数矩阵 matrix，以及一个整数 k，要求找到矩阵中一个非空子矩阵，使得其元素和最大，同时满足该子矩阵的和能被 k 整除。
换句话说，我们需要在所有和能被 k 整除的子矩阵中，找出最大的那个和。
如果不存在这样的子矩阵，返回 0。

示例：

matrix = [[1, 2, 3],
          [4, 5, 6],
          [7, 8, 9]]
k = 3

可能的子矩阵 [[1, 2], [4, 5]] 和为 12，能被 3 整除，但最大的是整个矩阵的和 45，也能被 3 整除，所以答案是 45。

2. 问题理解与核心难点

• 暴力枚举所有子矩阵是 O(m² n²) 的复杂度，不可接受。
• 关键在于：我们要找 最大子矩阵和，但附加了 和 mod k == 0 这个条件。
• 直接的最大子矩阵和（Kadane 算法在二维的推广）不适用于带模运算的条件。
• 核心思路：
  我们可以枚举矩阵的上下边界，将每一列在上下边界内的元素压缩成一个一维数组（列和数组），然后在这个一维数组上寻找 和能被 k 整除的最大子数组。

3. 从一维问题入手

先看一维问题：
给定数组 arr，求一个子数组，使得其和能被 k 整除，并且和最大。

一维问题解法：

1. 计算前缀和 prefix[i] 表示 arr[0..i-1] 的和。
2. 对于任意子数组 arr[i..j]，其和 = prefix[j+1] - prefix[i]。
3. 我们要求 (prefix[j+1] - prefix[i]) % k == 0，即 prefix[j+1] % k == prefix[i] % k。
4. 所以问题转化为：遍历前缀和，对于当前的 prefix[r] % k，我们要找之前出现过的同余的最小前缀和 prefix[l]，使得 prefix[r] - prefix[l] 最大。
5. 为什么找最小的 prefix[l]？因为 prefix[r] - prefix[l] 要最大，prefix[l] 就要尽可能小。
6. 我们维护一个哈希表 modMap，记录每个余数出现的最小前缀和。
7. 注意：前缀和可能是负数，模运算要注意处理为 (prefix % k + k) % k 的非负余数。
8. 初始化：modMap[0] = 0，因为余数为 0 时，可以选择空子数组（和为 0）。

一维问题代码框架（Python 风格）：

def max_sum_divisible_k_1d(arr, k):
    prefix = 0
    mod_map = {0: 0}  # 余数 -> 最小前缀和
    ans = float('-inf')
    for num in arr:
        prefix += num
        r = prefix % k
        if r in mod_map:
            ans = max(ans, prefix - mod_map[r])
        # 更新该余数的最小前缀和
        if r not in mod_map or prefix < mod_map[r]:
            mod_map[r] = prefix
    return ans if ans != float('-inf') else 0

4. 扩展到二维

二维的步骤：

1. 枚举上边界 top（从 0 到 m-1）。
2. 枚举下边界 bottom（从 top 到 m-1）。
3. 对于每一列 col，计算从 top 到 bottom 的和，得到一个长度为 n 的列和数组 col_sum。
4. 在 col_sum 上运行上述一维算法，得到在当前上下边界下的最大满足条件的子矩阵和。
5. 所有结果中取最大值。

复杂度：
枚举上下边界 O(m²)，每次运行一维算法 O(n)，总复杂度 O(m² n)。
如果 m > n，可以转置矩阵，保证 O(min(m,n)² * max(m,n))。

5. 逐步演算示例

以示例为例：

matrix = [[1, 2, 3],
          [4, 5, 6],
          [7, 8, 9]]
k = 3

• 枚举上边界 top=0，下边界 bottom=0：
  列和数组 = [1, 2, 3]
  前缀和变化：

  • prefix=1, r=1, mod_map{0:0}，无匹配
  • prefix=3, r=0, 匹配 mod_map[0]=0，子数组和=3，更新 ans=3
  • prefix=6, r=0, 匹配 mod_map[0]=0，子数组和=6，更新 ans=6
    此时最大=6。

• top=0, bottom=1：
  列和 = [1+4, 2+5, 3+6] = [5,7,9]
  前缀和：

  • 5 → r=2, 无匹配
  • 12 → r=0, 匹配 0，子数组和=12，ans=12
  • 21 → r=0, 匹配 0，子数组和=21，ans=21

• top=0, bottom=2：
  列和 = [1+4+7, 2+5+8, 3+6+9] = [12,15,18]
  前缀和：

  • 12 → r=0, 匹配 0，和=12，ans=21
  • 27 → r=0, 匹配 0，和=27，ans=27
  • 45 → r=0, 匹配 0，和=45，ans=45

• top=1, bottom=1：
  列和=[4,5,6]
  前缀和：

  • 4 → r=1, 无
  • 9 → r=0, 和=9，ans=45
  • 15 → r=0, 和=15，ans=45

• top=1, bottom=2：
  列和=[11,13,15]
  前缀和：

  • 11→r=2
  • 24→r=0, 和=24
  • 39→r=0, 和=39，ans=45

• top=2, bottom=2：
  列和=[7,8,9]
  前缀和：

  • 7→r=1
  • 15→r=0, 和=15
  • 24→r=0, 和=24
    ans=45

最终结果 45。

6. 边界处理

• 所有元素为负数且 k>0 的情况：如果没有任何子矩阵能被 k 整除，应返回 0（因为题目要求非空子矩阵，但如果没有满足条件的，和为 0 通常表示不存在，题目可能要求返回 0）。
• k=0 的情况：这时要求子矩阵和 = 0，其实是经典的最大和为 0 的子矩阵问题，做法类似，只是模运算改为判断相等。
• 一维算法中初始化 mod_map[0] = 0 很重要，它允许我们取整个前缀数组作为子数组。

7. 代码实现（Python）

def maxSumDivisibleK(matrix, k):
    if not matrix or not matrix[0]:
        return 0
    m, n = len(matrix), len(matrix[0])
    ans = float('-inf')
    # 保证 m <= n，否则转置
    if m > n:
        # 转置矩阵
        new_mat = [[matrix[j][i] for j in range(m)] for i in range(n)]
        return maxSumDivisibleK(new_mat, k)
    
    # 枚举上下边界
    for top in range(m):
        col_sum = [0] * n
        for bottom in range(top, m):
            for col in range(n):
                col_sum[col] += matrix[bottom][col]
            # 在 col_sum 上运行一维算法
            prefix = 0
            mod_map = {0: 0}
            for s in col_sum:
                prefix += s
                r = prefix % k
                if r in mod_map:
                    ans = max(ans, prefix - mod_map[r])
                if r not in mod_map or prefix < mod_map[r]:
                    mod_map[r] = prefix
    return 0 if ans == float('-inf') else ans

8. 总结

1. 核心转化：将二维子矩阵问题通过枚举上下边界压缩成一维子数组问题。
2. 一维关键：利用同余性质 (sum[j] - sum[i]) % k == 0 等价于 sum[j] % k == sum[i] % k，并用哈希表记录每个余数对应的最小前缀和。
3. 复杂度：O(m² n)（当 m ≤ n 时），可通过转置优化。
4. 适用场景：这种“和能被 k 整除”的条件可以推广到其他类似模运算约束的最大子数组/子矩阵问题。