Pythonで「厳密に増加してから減少する」最長部分リスト（山型）の長さを求める方法

問題概要

数値のリスト nums が与えられます。この中から、値が厳密に増加した後に厳密に減少する（山型の形状、最小長3）最長の部分リストの長さを求めます。

例えば、入力が nums = [8, 2, 4, 6, 3, 1] の場合、部分リスト [2, 4, 6, 3, 1] が厳密に増加してから減少しているため、出力は 5 となります。

アルゴリズムの考え方

この問題は、リストを先頭から走査しながら、増加区間と減少区間の長さをそれぞれ記録することで解決できます。手順は以下の通りです。

• i := 0、n := リストaのサイズ、res := 負の無限大 で初期化します。
• i < n - 2 の間、次の処理を繰り返します。
  • 区間の開始位置を st := i として記録します。
  • 増加カウンタ linc := 0、減少カウンタ ldec := 0 を初期化します。
  • i < n - 1 かつ a[i] < a[i + 1] の間、linc を1ずつ増やしながら i を進めます（厳密な増加区間を検出）。
  • i < n - 1 かつ a[i] > a[i + 1] の間、ldec を1ずつ増やしながら i を進めます（厳密な減少区間を検出）。
  • linc > 0 かつ ldec > 0 の場合（増加と減少の両方が存在する場合）、res := max(res, i - st + 1) として答えを更新します。
  • i < n - 1 かつ a[i] == a[i + 1] の間、i を進めて等しい要素をスキップします。
• 最後に、res >= 0 であれば res を返し、条件を満たす部分リストが存在しなければ 0 を返します。

実装例

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

class Solution:
    def solve(self, a):
        i, n, res = 0, len(a), float("-inf")
        while i < n - 2:
            st = i
            linc, ldec = 0, 0
            while i < n - 1 and a[i] < a[i + 1]:
                linc += 1
                i += 1
            while i < n - 1 and a[i] > a[i + 1]:
                ldec += 1
                i += 1
            if linc > 0 and ldec > 0:
                res = max(res, i - st + 1)
            while i < n - 1 and a[i] == a[i + 1]:
                i += 1
        return res if res >= 0 else 0

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

入力

[8, 2, 4, 6, 3, 1]

出力

5

計算量について

このアルゴリズムはリストを先頭から末尾まで一度だけ走査するため、時間計算量は O(n) となります。また、使用する変数はごくわずかなので、空間計算量も O(1) で済みます。隣接要素同士の比較だけで山型のパターンを検出できる、シンプルかつ効率的な手法です。