【Python】値の差とインデックスの差が一致する部分列の最大合計を求める方法

nums という数値のリストがあるとします。このリストから、「値が狭義に増加しており、かつ任意の2つの値の差が、それぞれのインデックス（位置）の差と一致する」という条件を満たす部分列を選びます。そして、そのような部分列の合計の最大値を求めることが目的です。

たとえば、入力が nums = [6, 7, 9, 9, 8, 5] の場合、出力は 22 になります。これは、部分列 [6, 7, 9]（対応するインデックスは [0, 1, 3]）を選ぶと、隣接する値同士の差が [1, 2] となり、これがインデックスの差と一致するためです。

解法のアプローチ

この問題を解くために、以下の手順に従います。

• d を空のマップ（辞書）として初期化します
• nums の各インデックス i と各値 x について、次の処理を行います
  • d[x − i] に x を加算します（d[x − i] := d[x − i] + x）
• d のすべての値の中から最大値を返します

ここでのポイントは「x − i」というキーです。ある要素について「値 − インデックス」の結果が同じであれば、それらの要素は「値の差 ＝ インデックスの差」という条件を満たす同一のグループに属することになります。したがって、同じキーを持つ要素の値をすべて合計すれば、条件を満たす部分列の合計が自然に得られます。

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

実装例

class Solution:
    def solve(self, nums):
        from collections import defaultdict
        d = defaultdict(int)
        for i, x in enumerate(nums):
            d[x - i] += x
        return max(d.values())

ob1 = Solution()
nums = [6, 7, 9, 9, 8, 5]
print(ob1.solve(nums))

入力

[6, 7, 9, 9, 8, 5]

出力

22

計算量について

このアルゴリズムの時間計算量は O(n)、空間計算量も O(n) です。リストを一度走査するだけで答えが求まるため、非常に効率的な解法と言えます。defaultdict を使うことで、キーの存在チェックを省略でき、コードも簡潔になります。