Pythonでリスト内の最長の交互サブシーケンス（ジグザグ列）の長さを求めるプログラム

問題概要

数値のリスト nums が与えられたとき、「隣り合う2つの要素の差が正・負と交互に入れ替わる」ような最長の部分列（サブシーケンス）の長さを求めることを考えます。なお、最初の差が正から始まっても負から始まっても構いません。

たとえば入力が nums = [6, 10, 4, 2, 3, 9, 4, 7] の場合、答えは 6 になります。これは [6, 10, 2, 9, 4, 7] という部分列を選ぶと、その差が [4, -8, 7, -5, 3] となり、正と負がきれいに交互に現れるためです。

解決の手順（動的計画法）

この問題は動的計画法（DP）を使うと効率よく解けます。各インデックス i について、次の2つの状態を管理するのがポイントです。

• dp[i][0]：インデックス i で終わり、最後の差が「正」である交互部分列の最大長
• dp[i][1]：インデックス i で終わり、最後の差が「負」である交互部分列の最大長

具体的なアルゴリズムは以下の通りです。

1. n := nums のサイズとする
2. dp := サイズ n × 2 のリストを作成し、すべて 1 で初期化する（要素1個だけでも長さ1の部分列としてカウントするため）
3. ans := 0 とする
4. i を 0 から n-1 まで繰り返す：
   • j を 0 から i-1 まで繰り返す：
     • nums[j] < nums[i] の場合：dp[i][0] = max(dp[i][0], dp[j][1] + 1)
     • nums[j] > nums[i] の場合：dp[i][1] = max(dp[i][1], dp[j][0] + 1)
   • ans = max(ans, dp[i][0], dp[i][1]) と更新する
5. ans を返す

この手法では、上昇で終わる列と下降で終わる列を交互につなぎ合わせることで、正負が交互になる条件を自然に満たせます。計算量は O(n²) であり、二重ループによる全ペアの比較が必要です。

Pythonでの実装例

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

class Solution:
    def solve(self, nums):
        n = len(nums)
        dp = [[1] * 2 for _ in range(n)]
        ans = 0
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i][0] = max(dp[i][0], dp[j][1] + 1)
                elif nums[j] > nums[i]:
                    dp[i][1] = max(dp[i][1], dp[j][0] + 1)
            ans = max(ans, dp[i][0], dp[i][1])
        return ans
ob = Solution()
nums = [6, 10, 4, 2, 3, 9, 4, 7]
print(ob.solve(nums))

入力

[6, 10, 4, 2, 3, 9, 4, 7]

出力

6