查找要删除的最短子数组以使数组在 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
米：=0
而p<=q，做
从循环中出来
在B的末尾插入arr[q]
当A不为空且A的最后一个元素>B的最后一个元素时，做
q:=q-1
从A中删除最后一个元素
在A的末尾插入arr[p]
p:=p+1
如果arr[p-1]<=arr[p]，则
否则当arr[q]<=arr[q+1]时，则
除此以外，
M:=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))输入
[10,20,30,100,40,20,30,50]输出结果
3