algorithm - 最大化两个数字的总和加上它们之间的距离

Question

我们给出了数字方阵，例如

1 9 2
3 8 3
2 1 1

相邻数字之间的距离是2。我们想在同一行或同一列中找到这样的两个数字，使得它们的和加上它们之间的距离最大。例如，在上面的示例中，这样的数字是 9 和 8，最大结果是 9+8+1*2 = 19。我们只想找到最大的结果，我们不需要具体数字的总和。

对我来说这看起来像是一个 DP 问题，但我想不出任何优雅的解决方案。

Answer 1

可以使用动态规划解决一维问题(即，给定一个数字列表，找到使和+距离最大化的对)。

bi = 0
best = -10**9  # anything large and negative
for i in range(1, n+1):
   best = max(best, a[i] + a[bi] + (i - bi)*2)
   if a[i] - i*2 > a[bi] - bi*2:
      bi = i

此代码完成后，best 将存储列表中任意一对数字的最大和 + 距离。它之所以有效，是因为在 i 的任何给定循环迭代中，bi 存储索引小于 i 的值的索引，该索引将其值减去两次最大化它的指数。可以观察到此索引处的数字是与 i 处的数字配对的最佳数字(i 左侧)。

有了这个之后，二维问题就很简单了:遍历每一行和每一列并应用一维算法，然后返回找到的最大对。总的来说，对于 n 乘 n 的矩阵，它的运行时间为 O(n^2)，这显然是渐近最优的，因为至少需要读取矩阵中的每个元素一次。

这是有效的 Python3 代码:

def max_sum_dist_1D(a):
    bi = 0
    best = -10**9
    for i in range(1, len(a)):
        best = max(best, a[i] + a[bi] + (i - bi)*2)
        if a[i] - i*2 > a[bi] - bi*2:
            bi = i
    return best

def max_sum_dist_2D(M):
    best_row = max(max_sum_dist_1D(row) for row in M)
    best_col = max(max_sum_dist_1D(col) for col in zip(*M))
    return max(best_row, best_col)

M = [[1, 9, 2], [3, 8, 3], [2, 1, 1]]

print(max_sum_dist_2D(M))