Chương trình tìm mảng con ngắn nhất cần xóa để mảng còn lại được sắp xếp trong Python

Giả sử có mảng arr, ta cần xóa một mảng con (subarray) sao cho các phần tử còn lại trong arr theo thứ tự không giảm (non-decreasing). Mục tiêu là tìm độ dài mảng con ngắn nhất cần xóa.

Ví dụ, với arr = [10,20,30,100,40,20,30,50], kết quả là 3 vì ta có thể xóa [100, 40, 20] (độ dài 3), mảng còn lại là [10,20,30,30,50] đã sắp xếp không giảm.

Các bước giải quyết:

• n := kích thước arr.
• Chèn 0 vào đầu và infinity vào cuối arr.
• Khởi tạo hai danh sách rỗng A, B.
• p := 1, q := kích thước arr - 2.
• M := 0.
• Trong khi p <= q:
  • Nếu arr[p-1] <= arr[p]: thêm arr[p] vào cuối A, tăng p lên 1.
  • Ngược lại nếu arr[q] <= arr[q+1]: thêm arr[q] vào cuối B; trong khi A không rỗng và phần tử cuối A > phần tử cuối B, xóa phần tử cuối A; giảm q đi 1.
  • Ngược lại: thoát vòng lặp.
  • M := max(M, len(A) + len(B)).
• Trả về n - M.

Ví dụ minh họa

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