在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 := 两个新的空列表
p := 1，q:= arr 的大小 -2
M := 0
while p <= q，执行
- 如果 arr[p-1] <= arr[p]，则
  - 将 arr[p] 插入到 A 的末尾
  - p := p + 1
- 否则当 arr[q] <= arr[q+1]，则
  - 将 arr[q] 插入到 B 的末尾
  - while A 不为空 and A 的最后一个元素 > B 的最后一个元素，执行
  - 从 A 中删除最后一个元素
  - q := q – 1
- 否则，
  - 退出循环
- M := A 的大小与 B 的大小之和的最大值
返回 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))