Pythonで最も長い交互不等式サブリストの長さを求めるプログラム

問題の概要

数値のリスト nums が与えられます。ここで求めたいのは、隣り合う数値どうしの大小関係(不等号)が「<(小なり)」と「>(大なり)」の間で交互に入れ替わるような、最も長いサブリストの長さです。なお、最初の2つの数値の大小関係は、小なり・大なりどちらから始めても構いません。

たとえば、入力が nums = [1, 2, 6, 4, 5] のとき、答えは 4 になります。これは、最も長い交互不等式サブリストが [2, 6, 4, 5] であり、2 < 6 > 4 < 5 というように不等号が交互に成立しているためです。

この種の上下に波打つ並びは「ジグザグ(波形)パターン」とも呼ばれ、「Longest Turbulent Subarray」など関連するアルゴリズム問題にも応用される重要な考え方です。

解法のアプローチ

リストを先頭から一度だけ走査し、直前の比較方向(増加か減少か)を覚えておくことで、O(n) の計算量で解くことができます。手順は次のとおりです。

• 関数 get_direction() を定義します。引数として a と b を受け取ります。

  • a と b が等しければ 0 を、a < b ならば -1 を、それ以外なら 1 を返します。

• nums のサイズが 2 未満の場合は、そのサイズをそのまま返します。

• max_length := 1、cur_length := 1、last_direction := 0 で初期化します。

• i を 0 から nums のサイズ − 2 まで(range(len(nums) - 1))繰り返します。

  • direction := get_direction(nums[i], nums[i + 1])

  • direction が 0 の場合(両者が等しい場合):cur_length := 1

  • direction が last_direction と等しい場合(前回と同じ方向の場合):cur_length := 2

  • それ以外の場合(方向が交互に切り替わった場合):cur_length := cur_length + 1

  • max_length := max_length と cur_length のうち大きい方

  • last_direction := direction

• max_length を返します。

ポイントは、「前回と同じ方向だった場合は cur_length を 2 に戻す」点です。これにより、方向が反転した瞬間から新しい交互パターンのカウントを正しくやり直せるようになります。

Pythonでの実装例

class Solution:
    def solve(self, nums):
        if len(nums) < 2:
            return len(nums)

        def get_direction(a, b):
            return 0 if a == b else -1 if a < b else 1

        max_length = 1
        cur_length = 1
        last_direction = 0

        for i in range(len(nums) - 1):
            direction = get_direction(nums[i], nums[i + 1])
            if direction == 0:
                cur_length = 1
            elif direction == last_direction:
                cur_length = 2
            else:
                cur_length += 1
            max_length = max(max_length, cur_length)
            last_direction = direction

        return max_length


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

入力

[1, 2, 6, 4, 5]

出力

4

処理の流れをトレース

入力 [1, 2, 6, 4, 5] の場合、ループ内の各変数は次のように変化します。

最終的に max_length は 4 となり、期待どおりの出力が得られます。

計算量について

リストを1回だけ走査するため、時間計算量は O(n) です。また、使用するのは定数個の変数のみなので、空間計算量は O(1) となります。大きな入力サイズに対しても非常に効率的に動作します。