Pythonの2つの数値リストから最大距離ペアを見つけるプログラム

AとBという2つの番号のリストがあり、それらの長さが同じであるとします。すべての0≤i

したがって、入力がA =[2、4、10、6] B =[3、4、7、5]の場合、i=0およびj=2の場合のように、出力は14になります。 2-10 | + | 3-7 | + |1-3|。

これを解決するには、次の手順に従います-

• ans：=0
• n：=aのサイズ
• [（-1、-1）、（-1、1）、（1、-1）、（1、1）]の各ペア（s、t）について、実行
  • cur_min：=無限大
  • cur_max：=-infinity
  • 0からnの範囲のiについては、
    • tmp：=s * a [i] + t * b [i] + i
    • cur_min：=cur_min、tmpの最小値
    • cur_max：=cur_max、tmpの最大値
  • ans：=ansの最大値、（cur_max --cur_min）
• 回答を返す

理解を深めるために、次の実装を見てみましょう-

例

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