Chương trình tìm mảng con ngắn nhất cần loại bỏ để sắp xếp mảng bằng Python

Giả sử chúng ta có một mảng được gọi là arr, chúng ta phải loại bỏ một mảng con của arr sao cho các phần tử còn lại trong arr có thứ tự không giảm. Chúng ta phải tìm độ dài của mảng con ngắn nhất để loại bỏ.

Vì vậy, nếu đầu vào là arr =[10,20,30,100,40,20,30,50], thì đầu ra sẽ là 3 vì chúng ta có thể loại bỏ [100, 40, 20] là mảng con nhỏ nhất có độ dài 3, và bằng cách xóa tất cả những thứ này theo thứ tự không giảm [10,20,30,30,50].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:

• n:=kích thước của arr
• arr:=chèn 0 vào bên trái arr và vô cực ở bên phải arr
• A, B:=hai danh sách trống mới
• p:=1, q:=kích thước của arr -2
• M:=0
• while p <=q, do
  • nếu arr [p-1] <=arr [p], thì
    • chèn arr [p] vào cuối A
    • p:=p + 1
  • ngược lại khi arr [q] <=arr [q + 1] thì
    • chèn arr [q] vào cuối B
    • while A không trống và phần tử cuối cùng của A> phần tử cuối cùng của B, thực hiện
      • xóa phần tử cuối cùng khỏi A
    • q:=q - 1
  • nếu không,
    • ra khỏi vòng lặp
  • M:=tối đa là M và kích thước A + kích thước B
• return n - M

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:

Ví dụ

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))

Đầu vào

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

Đầu ra

3