Pythonでリスト内の最長等差部分列の長さを求めるプログラム

問題の概要

数値のリスト nums が与えられたとき、そこから取り出せる「最長の等差数列（算術サブシーケンス）」の長さを求めます。ある数列 S が等差数列であるとは、すべての i（0 ≤ i < Sの長さ − 1）に対して、隣接する2項の差 S[i+1] − S[i] が常に同じ値になることを意味します。

たとえば、入力が nums = [1, 4, 7, 10, 13, 20, 16] の場合、答えは 6 になります。これは、部分列 [1, 4, 7, 10, 13, 16] を選ぶと、隣接する要素同士の差がすべて 3 で一定だからです。

解法のアプローチ：動的計画法（DP）

この問題は動的計画法を使って効率的に解けます。ポイントは、各インデックス i について「公差（差分）ごとの等差部分列の長さ」を記録していくことです。dp[(i, diff)] は「インデックス i で終わり、公差が diff である等差部分列の最大長」を表します。手順は以下の通りです。

• n := 配列 arr のサイズとします
• n ≤ 1 の場合は、そのまま n を返します
• res := 0（最終的な答えを保持する変数）
• dp := 空のマップ。キーが存在しない場合はデフォルト値として 1 を返すようにします
• i を 1 から n−1 まで繰り返します：
  • j を 0 から i−1 まで繰り返します：
    • diff := arr[i] − arr[j]
    • dp[i, diff] := dp[j, diff] + 1
    • res := res と dp[i, diff] のうち大きい方の値
• 最後に res を返します

このアルゴリズムの時間計算量は O(n²)、空間計算量も O(n²) であり、要素数が数千程度のリストであれば十分実用的な速度で動作します。

Pythonでの実装例

理解を深めるために、実際の Python コードを見てみましょう。

from collections import defaultdict
class Solution:
   def solve(self, arr):
      n = len(arr)
      if n <= 1:
         return n
      res = 0
      dp = defaultdict(lambda: 1)
      for i in range(1, n):
         for j in range(i):
            diff = arr[i] - arr[j]
            dp[i, diff] = dp[j, diff] + 1
            res = max(res, dp[i, diff])
      return res
ob = Solution()
nums = [1, 4, 7, 10, 13, 20, 16]
print(ob.solve(nums))

ここでは defaultdict(lambda: 1) を使うことで、まだキーが登録されていない (i, diff) の組み合わせに対しても自動的に初期値 1（要素1つだけの部分列）が割り当てられ、コードが簡潔になります。

入力例

[1, 4, 7, 10, 13, 20, 16]

出力例

6