如何求解可最多排除两个连续行区域的矩阵最优和子结构

简化版问题回顾 #

给定n×n整数矩阵，我们需要寻找满足特定限制的最大和子矩阵。在已解决的简化版本中，规则是：可以绘制一条水平线和一条45度右上方向的对角线，移除线下方及右侧的所有元素，只保留剩余区域的元素求和，找出最大和。

以下是一个10×10的示例矩阵：

[[ 1, -3, -2,  2, -1, -3,  0, -2,  0,  0],
 [-1,  3,  3, -3,  0, -1,  0,  0, -2, -2],
 [-1,  0, -1,  0,  2,  1,  1, -3,  2,  1],
 [-3,  1, -3, -1,  1, -3, -2, -1, -3,  1],
 [ 1, -3,  1, -2,  2,  1, -3,  2, -3,  0],
 [-1, -2,  0, -2,  2, -3,  3, -1, -1,  2],
 [ 2,  2, -3, -1,  0, -1,  2,  0,  3,  0],
 [-1,  3, -1,  1, -1,  0,  0,  3, -3,  0],
 [ 3,  2,  1,  1,  2,  3,  0,  2,  0, -3],
 [ 0,  3,  2,  0, -1, -2,  3, -3, -3,  1]]

这个版本下的最优和为3。若用square存储该二维数组，以下代码可以定位获得最大和的底行终点位置：

import numpy as np

max_sums = np.empty_like(square, dtype=np.int_)
max_sums[0] = np.cumsum(square[0])
for row_idx in range(1, dim):
    cusum = np.cumsum(square[row_idx])
    for col_idx in range(dim):
        if col_idx < dim - 1:
            max_sums[row_idx, col_idx] = cusum[col_idx] + max_sums[row_idx - 1, col_idx + 1]
        else:
            max_sums[row_idx, col_idx] = cusum[col_idx] + max_sums[row_idx - 1, col_idx]

maxes = np.argwhere(max_sums==max_sums.max())   # 找到所有最大值的位置
print(f"The coordinates of the maximums are {maxes} with sum {np.max(max_sums)}")

扩展问题需求 #

现在需要修改规则：寻找最大和时，允许排除由连续行组成的区域，且最多可排除两个这样的区域（简化版仅允许排除底部的一个行区域）。排除区域必须是整行，不能仅排除行的部分。

比如对上述示例矩阵，排除第0-1行和第3-5行后，重新计算可得最大和为26。需要实现能适配更大规模矩阵的解决方案。

内容的提问来源于stack exchange，提问作者Simd