Pythonで数値リストから最長の符号交互部分列の長さを求めるプログラム

問題の概要

数値リスト nums が与えられたとき、隣り合う要素ごとに符号が入れ替わる（正と負が交互に出現する）最長の部分列の長さを求めます。

例えば、nums = [1, 3, -6, 4, -3] の場合、[1, -6, 4, -3] を選ぶと符号が交互に入れ替わっているため、出力は 4 になります。

アルゴリズムの考え方

この問題は、動的計画法の考え方を用いることで O(n) の計算量で効率的に解くことができます。ポイントは次の 2 つの変数です。

• pos：「正の数で終わる符号交互部分列」の最大長を保持する
• neg：「負の数で終わる符号交互部分列」の最大長を保持する

具体的な手順は以下の通りです。

• pos := 0、neg := 0 として初期化する
• リスト内の各要素 n について次を繰り返す
  • n < 0 の場合：neg := pos + 1（正の数で終わる列に、この負の数を付け加えることができる）
  • それ以外の場合：pos := neg + 1（負の数で終わる列に、この非負の数を付け加えることができる）
• 最後に pos と neg の大きい方を返す

このように、各要素を一度だけ走査しながら状態を更新していくため、追加の配列も不要で空間計算量は O(1) に抑えられます。

実装例

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

class Solution:
   def solve(self, nums):
      pos = neg = 0
      for n in nums:
         if n < 0:
            neg = pos + 1
         else:
            pos = neg + 1
      return max(pos, neg)

ob = Solution()
nums = [1, 3, -6, 4, -3]
print(ob.solve(nums))

入力

[1, 3, -6, 4, -3]

出力

4

まとめ

本記事では、数値リストから「隣接する要素の符号が交互に入れ替わる最長部分列」の長さを求める方法を紹介しました。pos と neg の 2 つの変数だけで状態を管理できるシンプルな手法であり、時間計算量 O(n)・空間計算量 O(1) で実現できる点が魅力です。同様のパターンは、増減が交互に現れる系列を扱う他の DP 問題にも応用できるので、ぜひ覚えておきましょう。