Pythonで残りが昇順になるように削除すべき最短部分配列の長さを求める方法

配列 arr が与えられます。この配列から連続した部分配列(サブアレイ)をひとつ取り除いたとき、残りの要素が非減少順(昇順)に並ぶようにしたいとします。このとき、削除すべき最短の部分配列の長さを求めましょう。

たとえば、入力が arr = [10,20,30,100,40,20,30,50] の場合、答えは 3 になります。[100, 40, 20] という長さ3の部分配列を削除すると、残りは [10,20,30,30,50] となり、すべての要素が非減少順に整列するからです。

解法の考え方

この問題は、次の手順で解くことができます。

• n := 配列 arr のサイズ
• arr := 先頭に 0 を挿入し、末尾に無限大(float("inf"))を挿入して番兵(センチネル値)を置く
• A、B := 空のリストを2つ用意する
• p := 1、q := 配列のサイズ − 2(番兵を除いた実データの範囲)
• M := 0(残せる要素数の最大値)
• p <= q の間、以下を繰り返します
  • arr[p-1] <= arr[p] の場合:arr[p] を A の末尾に追加し、p を 1 増やす(左側からできるだけ延ばす)
  • それ以外で arr[q] <= arr[q+1] の場合:arr[q] を B の末尾に追加し、A の末尾に B の末尾より大きい要素がある間それらを取り除いてから、q を 1 減らす
  • どちらの条件も満たさない場合はループを抜ける
  • M := M と(A のサイズ + B のサイズ)の大きい方で更新する
• 最後に n - M(= 削除が必要な最小の長さ)を返す

ポイントは、左側(A)と右側(B)からそれぞれ非減少の並びを構築しながら、両者がうまくつながるように調整していく点です。先頭と末尾に番兵を置くことで、配列の端における境界条件の扱いがシンプルになります。

Pythonでの実装例

def solve(arr):
    n = len(arr)
    arr = [0] + arr + [float("inf")]
    A, B = [], []
    p, q = 1, len(arr) - 2
    M = 0
    while p <= q:
        if arr[p-1] <= arr[p]:
            A.append(arr[p])
            p += 1
        elif arr[q] <= arr[q+1]:
            B.append(arr[q])
            while A and A[-1] > B[-1]:
                A.pop()
            q -= 1
        else:
            break
        M = max(M, len(A) + len(B))
    return n - M

arr = [10,20,30,100,40,20,30,50]
print(solve(arr))

入力

[10,20,30,100,40,20,30,50]

出力

3

この結果から、長さ3の部分配列 [100, 40, 20] を削除すればよいことが正しく判定できていることがわかります。