Pythonで配列をソートするために削除する最短のサブ配列を見つけるプログラム

arrという配列があるとすると、arrの残りの要素が降順でないように、arrのサブ配列を削除する必要があります。削除する最短のサブアレイの長さを見つける必要があります。

したがって、入力がarr =[10,20,30,100,40,20,30,50]の場合、長さ3の最小のサブ配列である[100、40、20]を削除できるため、出力は3になります。そして、これらをすべて削除することにより、降順ではありません[10、20、30、30、50]。

これを解決するには、次の手順に従います。

• n：=arrのサイズ
• arr：=arrの左側に0を挿入し、arrの右側に無限大を挿入します
• A、B：=2つの新しい空のリスト
• p：=1、q：=arr-2のサイズ
• M：=0
• p <=qの場合、do
  • arr [p-1] <=arr [p]の場合、
    • Aの最後にarr[p]を挿入
    • p：=p + 1
  • それ以外の場合、arr [q] <=arr [q + 1]の場合、
    • Bの最後にarr[q]を挿入
    • Aが空ではなく、Aの最後の要素> Bの最後の要素である場合、
      • Aから最後の要素を削除する
    • q：=q-1
  • それ以外の場合、
    • ループから抜け出す
  • M：=Mの最大値とAのサイズ+Bのサイズ
• return n-M

理解を深めるために、次の実装を見てみましょう。

例

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