โปรแกรมหาสับอาร์เรย์สั้นที่สุดที่ต้องลบเพื่อให้อาร์เรย์เรียงลำดับไม่ลดลงใน Python

โจทย์

ให้อาร์เรย์ arr เราต้องลบสับอาร์เรย์ (subarray) หนึ่งช่วงออก เพื่อให้สมาชิกที่เหลือเรียงลำดับไม่ลดลง (non-decreasing) ต้องการหาความยาวของสับอาร์เรย์ที่สั้นที่สุดที่ต้องลบ

ตัวอย่าง: arr = [10,20,30,100,40,20,30,50] ผลลัพธ์คือ 3 เพราะลบ [100, 40, 20] (ความยาว 3) แล้วเหลือ [10,20,30,30,50] ที่เรียงไม่ลดลง

อัลกอริทึม

1. ให้ n เป็นขนาดของ arr
2. เพิ่มค่า 0 ด้านซ้ายและ infinity ด้านขวาของ arr
3. สร้างลิสต์ว่าง A และ B
4. กำหนด p = 1, q = len(arr) - 2, M = 0
5. วนลูป بينما p ≤ q:
   • ถ้า arr[p-1] ≤ arr[p]: เพิ่ม arr[p] ลง A, เพิ่ม p
   • มิฉะนั้นถ้า arr[q] ≤ arr[q+1]: เพิ่ม arr[q] ลง B, แล้วลบสมาชิกท้ายของ A ทั้งหมดที่มากกว่าสมาชิกท้ายของ B, ลด q
   • มิฉะนั้น: ออกจากลูป
6. อัปเดต M = max(M, len(A) + len(B))
7. คืนค่า 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))  # Output: 3

อินพุต / เอาต์พุต

Input: [10,20,30,100,40,20,30,50]
Output: 3