【Python】1つの要素を削除して作れる最長の連続増加部分リストの長さを求めるアルゴリズム

問題概要

数値のリスト nums が与えられたとき、最大で1つの要素を削除できるという条件のもとで、連続した「厳密に増加する」部分リスト（サブリスト）の最大の長さを求めます。ここで「厳密に増加する」とは、隣り合う要素が必ず前より大きくなっている状態を指します。

例えば、入力が nums = [35, 5, 6, 7, 8, 9, 12, 11, 26] の場合、答えは 7 になります。これは、リストから 12 を削除すると [5, 6, 7, 8, 9, 11, 26] となり、この部分リストの長さが7で、これ以上長い連続増加部分リストは存在しないためです。

解法のアプローチ：両方向からのDP

この問題は、動的計画法（DP）の考え方を使うことで効率的に解けます。ポイントは、各位置について「そこで終わる増加列の長さ」と「そこから始まる増加列の長さ」をそれぞれ事前に計算しておくことです。

アルゴリズムの手順

• nums が空の場合は 0 を返します。
• end: nums と同じサイズのリストを作り、すべて 1 で初期化します。end[i] は「インデックス i で終わる連続増加列の長さ」を表します。
• start: 同じく同じサイズのリストを 1 で初期化します。start[j] は「インデックス j から始まる連続増加列の長さ」を表します。
• i を 1 から len(nums) - 1 まで順に処理し、nums[i] > nums[i - 1] であれば end[i] = end[i - 1] + 1 と更新します。
• j を len(nums) - 2 から 0 まで逆順に処理し、nums[j + 1] > nums[j] であれば start[j] = start[j + 1] + 1 と更新します。
• res を end と start の全要素の最大値として初期化します（何も削除しないケース）。
• k を 1 から len(nums) - 2 まで順に処理し、「k 番目の要素を削除する」ケースを検討します。nums[k - 1] < nums[k + 1] が成り立てば、削除によって両側の増加列をつなげられるので、res を max(res, end[k - 1] + start[k + 1]) で更新します。
• 最後に res を返します。

実装例

以下が実際のPythonコードです。

def solve(nums):
    if not nums:
        return 0
    end = [1 for i in nums]
    start = [1 for i in nums]

    # 左から右へ：各位置で終わる増加列の長さ
    for i in range(1, len(nums)):
        if nums[i] > nums[i - 1]:
            end[i] = end[i - 1] + 1

    # 右から左へ：各位置から始まる増加列の長さ
    for j in range(len(nums) - 2, -1, -1):
        if nums[j + 1] > nums[j]:
            start[j] = start[j + 1] + 1

    # 要素を削除しない場合の最大値
    res = max(max(end), max(start))

    # 1つの要素を削除して増加列をつなげる場合
    for k in range(1, len(nums) - 1):
        if nums[k - 1] < nums[k + 1]:
            res = max(res, end[k - 1] + start[k + 1])

    return res

nums = [35, 5, 6, 7, 8, 9, 12, 11, 26]
print(solve(nums))

入力

[35, 5, 6, 7, 8, 9, 12, 11, 26]

出力

7

計算量について

このアルゴリズムは、リストを前方向・後ろ方向・中間チェックの合計3回走査するだけなので、時間計算量は O(n)、補助配列2つ分の領域が必要なため空間計算量も O(n) となります。全ての削除候補を毎回試す総当たり方式（O(n²)）よりも大幅に効率的です。