方阵中同行或同列两数之和加间距的最大值求解

架构老林

2026-5-21

解决这个方阵最大和+距离问题的高效思路

其实这个问题完全不用复杂的动态规划，我们可以通过数学变形把它简化成线性遍历的问题，效率很高，时间复杂度是O(n*m)（n是行数，m是列数）。

不管是同一行还是同一列，我们先把目标公式拆解开：

对于同一行：假设两个数是matrix[i][j]和matrix[i][k]（j < k），它们的总价值是：
```
matrix[i][j] + matrix[i][k] + 2*(k - j)
```
把式子整理一下，就能拆成：
```
(matrix[i][j] - 2*j) + (matrix[i][k] + 2*k)
```
看到没？对于每个位置k，我们只需要找到该行中j < k时(matrix[i][j] - 2*j)的最大值，再加上当前的(matrix[i][k] + 2*k)，就能得到该行中以k为右端点的最大总价值。
对于同一列：类似地，两个数matrix[i][j]和matrix[k][j]（i < k）的总价值是：
```
matrix[i][j] + matrix[k][j] + 2*(k - i)
```
整理后变成：
```
(matrix[i][j] - 2*i) + (matrix[k][j] + 2*k)
```
同样的逻辑，遍历每一列时，记录上方(matrix[i][j] - 2*i)的最大值，和当前的(matrix[k][j] + 2*k)相加，得到该列中以k为下端点的最大总价值。

初始化全局最大值为负无穷（确保能被任何有效结果覆盖）。
遍历每一行：
- 对于当前行，先记录第一个元素对应的(matrix[i][0] - 2*0)作为当前行的最大值前缀。
- 从第二个元素开始遍历，计算当前元素的(matrix[i][k] + 2*k)加上前缀最大值，得到当前可能的总价值，和全局最大值比较更新。
- 然后更新前缀最大值为max(前缀最大值, matrix[i][k] - 2*k)（因为后面的元素会用到这个值）。
遍历每一列：
- 对于当前列，先记录第一个元素对应的(matrix[0][j] - 2*0)作为当前列的最大值前缀。
- 从第二个元素开始遍历，计算当前元素的(matrix[k][j] + 2*k)加上前缀最大值，得到当前可能的总价值，和全局最大值比较更新。
- 然后更新前缀最大值为max(前缀最大值, matrix[k][j] - 2*k)。
遍历结束后，全局最大值就是我们要的结果。

拿你给的3×3矩阵[[1,9,2],[3,8,3],[2,1,1]]来测试：

第一行遍历：
- 第一个元素：1 - 2*0 = 1（前缀最大值=1）
- 第二个元素：9 + 2*1 = 11，加上前缀1得12，全局最大暂时是12；然后更新前缀为max(1, 9-2*1)=7
- 第三个元素：2 + 2*2=6，加前缀7得13，全局最大更新为13；前缀更新为max(7,2-2*2)=7
第二行遍历：
- 第一个元素：3-0=3（前缀=3）
- 第二个元素：8+2*1=10，加3得13，全局最大还是13；前缀更新为max(3,8-2*1)=6
- 第三个元素：3+2*2=7，加6得13，全局不变；前缀更新为max(6,3-2*2)=6
第三行遍历：
- 第一个元素：2-0=2（前缀=2）
- 第二个元素：1+2*1=3，加2得5，全局不变；前缀更新为max(2,1-2*1)=2
- 第三个元素：1+2*2=5，加2得7，全局不变
然后遍历列：
- 第一列：
  - 第一个元素：1-0=1（前缀=1）
  - 第二个元素：3+2*1=5，加1得6，全局不变；前缀更新为max(1,3-2*1)=1
  - 第三个元素：2+2*2=6，加1得7，全局不变
- 第二列：
  - 第一个元素：9-0=9（前缀=9）
  - 第二个元素：8+2*1=10，加9得19，全局最大更新为19；前缀更新为max(9,8-2*1)=9
  - 第三个元素：1+2*2=5，加9得14，全局不变
- 第三列：
  - 第一个元素：2-0=2（前缀=2）
  - 第二个元素：3+2*1=5，加2得7，全局不变；前缀更新为max(2,3-2*1)=2
  - 第三个元素：1+2*2=5，加2得7，全局不变
    最终全局最大值就是19，和示例结果一致。

这个方法简单高效，完全不需要复杂的DP状态转移，线性遍历就能解决问题。

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