Pythonで1つの要素を削除して作れる最長の連続増加サブリストの長さを求める方法

問題の概要

数値のリスト nums が与えられます。ここで、リストから0個または1個の要素を削除できるものとし、その結果として得られる「連続した厳密に増加する部分リスト（サブリスト）」の最大の長さを求めます。

たとえば、入力が nums = [30, 11, 12, 13, 14, 15, 18, 17, 32] の場合、答えは 7 になります。18 を削除すれば [11, 12, 13, 14, 15, 17, 32] という最も長い連続した厳密増加部分リストが得られ、その長さがちょうど 7 になるためです。

解法の考え方

この問題は、次の2つの配列を用意すると効率よく解けます。

• pre[i]：インデックス i で終わる、連続した厳密増加列の長さ
• suff[i]：インデックス i から始まる、連続した厳密増加列の長さ

これらが求まれば、答えは次の2パターンの最大値になります。

1. 何も削除しない場合：max(pre) と max(suff) の大きい方
2. インデックス i の要素を1つ削除する場合：nums[i-1] < nums[i+1] が成り立てば、pre[i-1] + suff[i+1] によって前後の増加列をつなげられる

アルゴリズムの手順

• n := nums のサイズとする
• pre := サイズ n のリストを、すべて 1 で初期化する
• i を 1 から n-1 まで順に処理する：nums[i] > nums[i-1] ならば、pre[i] := pre[i-1] + 1 とする
• suff := サイズ n のリストを、すべて 1 で初期化する
• i を n-2 から 0 まで逆順に処理する：nums[i] < nums[i+1] ならば、suff[i] := suff[i+1] + 1 とする
• ans := max(pre) と max(suff) の最大値とする
• i を 1 から n-2 まで順に処理する：nums[i-1] < nums[i+1] ならば、ans := max(ans, pre[i-1] + suff[i+1]) とする
• ans を返す

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

Pythonでの実装例

class Solution:
    def solve(self, nums):
        n = len(nums)
        pre = [1] * n
        for i in range(1, n):
            if nums[i] > nums[i - 1]:
                pre[i] = pre[i - 1] + 1
        suff = [1] * n
        for i in range(n - 2, -1, -1):
            if nums[i] < nums[i + 1]:
                suff[i] = suff[i + 1] + 1
        ans = max(max(pre), max(suff))
        for i in range(1, n - 1):
            if nums[i - 1] < nums[i + 1]:
                ans = max(ans, pre[i - 1] + suff[i + 1])
        return ans

ob = Solution()
nums = [30, 11, 12, 13, 14, 15, 18, 17, 32]
print(ob.solve(nums))

入力

[30, 11, 12, 13, 14, 15, 18, 17, 32]

出力

7

計算量について

pre と suff の構築にそれぞれ O(n)、答えの集計にも O(n) しかかからないため、全体の時間計算量は O(n) です。また、補助配列として pre と suff を保持するため、空間計算量も O(n) となります。全要素の組み合わせを調べる総当たり方式（O(n²) 以上）と比べて、非常に効率的な解法だと言えます。