Pythonで指定した差を持つ最長等差部分列の長さを求めるプログラム

数値のリスト nums と整数 diff が与えられたとき、隣り合う要素同士の差がすべて diff と一致するような最長の等差部分列(算術サブシーケンス)の長さを求める問題を考えます。

たとえば、nums = [-1, 1, 4, 7, 2, 10]、diff = 3 の場合を考えてみましょう。このとき、部分列 [1, 4, 7, 10] を選ぶことができ、各要素間の差はすべて 3 になるため、答えは 4 となります。

解法のアプローチ

この問題は動的計画法(DP)の考え方を使うと効率的に解けます。各値について「その値で終わる等差部分列の最大長」を辞書に記録しながら、リストを一度走査するだけで答えが求まります。具体的な手順は以下の通りです。

• seen:各値をキーとし、「その値で終わる等差部分列の長さ」を格納する辞書。キーが存在しない場合のデフォルト値は 0。
• mx:これまでに見つかった最長の長さ。初期値は 0。
• リスト内の各要素 x に対して以下を繰り返します。
  • x - diff が seen に存在する場合は、seen[x] := seen[x - diff] + 1 とする。
  • 存在しない場合は、seen[x] := 1 とする(その要素単体で長さ 1 の部分列となるため)。
• mx を mx と seen[x] の最大値で更新します。
• 最後に mx を返します。

実装例(Python)

それでは、実際のコード実装を見て理解を深めましょう。

from collections import defaultdict

def solve(nums, diff):
    seen = defaultdict(int)
    mx = 0
    for x in nums:
        if x - diff in seen:
            seen[x] = seen[x - diff] + 1
        else:
            seen[x] = 1
        mx = max(mx, seen[x])
    return mx

nums = [-1, 1, 4, 7, 2, 10]
diff = 3
print(solve(nums, diff))

入力

[-1, 1, 4, 7, 2, 10], 3

出力

4

計算量について

このアルゴリズムはリストを一度だけ走査し、各ステップでの辞書操作は O(1) で行えるため、時間計算量は O(n)、空間計算量も O(n) となります(n はリストの要素数)。素朴な全探索では O(n²) 以上かかるところを、この方法なら線形時間で効率よく解くことができます。