Pythonで隣接要素間の絶対差がk以下となる最長部分列の長さを求める方法

数値のリスト nums と整数 k が与えられたとき、「隣接する要素同士の絶対差がすべて k 以下」という条件を満たす最長の部分列(サブシーケンス)の長さを求める問題を考えてみましょう。

たとえば、入力が nums = [5, 6, 2, 1, -6, 0, -1]、k = 4 の場合、答えは 6 になります。

アプローチ：セグメント木による効率的な解法

この問題を素朴な動的計画法で解くと O(n²) の計算量が必要になり、要素数が多い場合には非効率です。そこでセグメント木(segment tree)を活用すると、各要素の処理を O(log n) に抑えられ、全体を O(n log n) で解くことができます。

基本的なアイデアは次のとおりです。

• 配列をソートし、値をインデックスに対応付ける(座標圧縮)。
• 各要素 x について、値が [x - k, x + k] の範囲内にある要素から伸びる最長部分列の長さの最大値を、セグメント木への区間最大値クエリで取得する。
• その最大値 + 1 を現在の要素での部分列の長さとしてセグメント木に書き戻す。

アルゴリズムの手順

• update(i, x):位置 i の値を x で更新する関数を定義します。
  • i := i + n
  • i が 0 でない間、次を繰り返します。
    • segtree[i] := max(segtree[i], x)
    • i := i / 2(親ノードへ移動)
• query(i, j):区間 [i, j] の最大値を取得する関数を定義します。
  • ans := -∞
  • i := i + n、j := j + n + 1
  • i < j の間、次を繰り返します。
    • i が奇数なら ans := max(ans, segtree[i]) とし、i := i + 1
    • j が奇数なら j := j - 1 とし、ans := max(ans, segtree[j])
    • i := i / 2、j := j / 2
  • ans を返します。
• メイン処理では、次のように進めます。
  • n = 2^(log2(len(nums) + 1) + 1) としてセグメント木のサイズを決めます。
  • snums := nums をソートしたリスト
  • index := 各値 x をソート後のインデックスに対応付けた辞書
  • ans := 0
  • nums の各要素 x について:
    • lo := x - k をソート順を保ったまま挿入できる最左位置(bisect_left)
    • hi := x + k を挿入できる最左位置 - 1(bisect_right)
    • count := query(lo, hi)
    • update(index[x], count + 1)
    • ans := max(ans, count + 1)
  • ans を返します。

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

実装例

import math, bisect

class Solution:
    def solve(self, nums, k):
        n = 2 ** int(math.log2(len(nums) + 1) + 1)
        segtree = [0] * 100000

        def update(i, x):
            i += n
            while i:
                segtree[i] = max(segtree[i], x)
                i //= 2

        def query(i, j):
            ans = -float('inf')
            i += n
            j += n + 1
            while i < j:
                if i % 2 == 1:
                    ans = max(ans, segtree[i])
                    i += 1
                if j % 2 == 1:
                    j -= 1
                    ans = max(ans, segtree[j])
                i //= 2
                j //= 2
            return ans

        snums = sorted(nums)
        index = {x: i for i, x in enumerate(snums)}
        ans = 0
        for x in nums:
            lo = bisect.bisect_left(snums, x - k)
            hi = bisect.bisect_right(snums, x + k) - 1
            count = query(lo, hi)
            update(index[x], count + 1)
            ans = max(ans, count + 1)
        return ans

ob = Solution()
print(ob.solve([5, 6, 2, 1, -6, 0, -1], 4))

入力

[5, 6, 2, 1, -6, 0, -1], 4

出力

6