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

Question

我们给出方数矩阵,例如

1 9 2
3 8 3
2 1 1

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

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

Answer 1

可以使用动态编程解决1D问题(即,给定数字列表,找到最大化和+距离的对).

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与at配对的最佳数字(在左侧).

一旦你有了这个,2D问题很简单:遍历每一行和每一行并应用1D算法,并返回找到的最大对.整体用于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))