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

問題の概要

同じ長さ n を持つ2つの数値リスト 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| + |0 − 2| = 8 + 4 + 2 = 14 となるためです。

解法のアプローチ

すべてのペア (i, j) を総当たりで調べると計算量は O(n²) になりますが、絶対値の性質を利用すると O(n) まで削減できます。任意の実数 x に対して |x| は符号 s ∈ {−1, 1} を用いた s × x の最大値として表せるため、符号の組み合わせ (s, t) それぞれについて「s × a[i] + t × b[i] + i」という式の最大値と最小値の差を求め、その中で最も大きいものが答えになります。

具体的な手順は以下の通りです。

• ans := 0 で初期化する
• n := リスト a のサイズとする
• (s, t) の各組み合わせ [(-1, -1), (-1, 1), (1, -1), (1, 1)] について以下を実行する
  • cur_min := 正の無限大
  • cur_max := 負の無限大
  • i を 0 から n−1 まで繰り返す
    • 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)
• ans を返す

実装例

理解を深めるために、以下の実装を見てみましょう。

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

まとめ

この手法では、絶対値を含む式を符号の組み合わせごとに分解することで、リストを1回走査するだけで最大値と最小値を取得でき、全体の計算量を O(n) に抑えられます。総当たり方式と比べて大幅に高速なため、要素数の多いリストでも効率的に最大距離ペアを求められる実用的なアルゴリズムです。