在 Python 中查找两个数字列表中的最大距离对的程序

在 Python 中查找两个数字列表中的最大距离对的程序

假设我们有两个名为 A 和 B 的数字列表,它们的长度相同。我们必须找到所有 0 ≤ i < j < n 情况下的最大值:|a[i] – a[j]| + |b[i] – b[j]| + |i – j|

因此,如果输入为 A = [2, 4, 10, 6] B = [3, 4, 7, 5],那么输出将是 14,因为当 i = 0,j = 2 时,我们得到了 |2 – 10| + |3 – 7| + |1 – 3|。

要解决这个问题,我们将遵循以下步骤 −

  • ans := 0
  • n := a 的长度
  • 对于 [(-1, -1) ,(-1, 1) ,(1, -1) ,(1, 1) ] 中的每个组合 (s, t),做以下操作
    • cur_min := 无穷大
    • cur_max := 负无穷大
    • 对于 i 在范围 0 到 n 的每个数,做以下操作
      • tmp := s * a[i] + t * b[i] + i
      • cur_min := cur_min 和 tmp 中的最小值
      • cur_max := cur_max 和 tmp 中的最大值
    • ans := ans 和 (cur_max – cur_min) 中的最大值
  • 返回 ans

让我们看看以下实现以更好地理解 −

更多Python相关文章,请阅读:Python 教程

示例

class Solution:
   def solve(self, a, b):
      ans = 0
      n = len(a)
      for s, t in [(-1, -1), (-1, 1), (1, -1), (1, 1)]:
         cur_min = float("inf")
         cur_max = float("-inf")
         for i in range(n):
            tmp = s * a[i] + t * b[i] + i
            cur_min = min(cur_min, tmp)
            cur_max = max(cur_max, tmp)
            ans = max(ans, cur_max - cur_min)
      return ans
ob = Solution()
A = [2, 4, 10, 6]
B = [3, 4, 7, 5]
print(ob.solve(A, B))

输入

[2, 4, 10, 6],[3, 4, 7, 5]

输出

14

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程