สมมติว่าเรามีอาร์เรย์ที่เรียกว่า arr เราต้องลบอาร์เรย์ย่อยของ arr เพื่อให้องค์ประกอบที่เหลืออยู่ใน arr อยู่ในลำดับที่ไม่ลดลง เราต้องหาความยาวของ subarray ที่สั้นที่สุดเพื่อลบออก
ดังนั้น หากอินพุตเป็นเหมือน arr =[10,20,30,100,40,20,30,50] ผลลัพธ์จะเป็น 3 เพราะเราสามารถลบ [100, 40, 20] ซึ่งเป็นอาร์เรย์ย่อยที่เล็กที่สุดของความยาว 3 และโดยการลบสิ่งเหล่านี้ทั้งหมดจะไม่ลดลง [10,20,30,30,50]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
- n :=ขนาดของ arr
- arr :=ใส่ 0 ที่ด้านซ้ายของ arr และอินฟินิตี้ที่ด้านขวาของ arr
- A,B :=สองรายการที่ว่างเปล่าใหม่
- p :=1, q:=ขนาดของ arr -2
- ม :=0
- ในขณะที่ p <=q ทำ
- ถ้า arr[p-1] <=arr[p] แล้ว
- ใส่ arr[p] ที่ส่วนท้ายของ A
- p :=p + 1
- มิฉะนั้น เมื่อ arr[q] <=arr[q+1] แล้ว
- ใส่ arr[q] ที่ส่วนท้ายของ B
- ในขณะที่ A ไม่ว่างเปล่าและองค์ประกอบสุดท้ายของ A> องค์ประกอบสุดท้ายของ B ให้ทำ
- ลบองค์ประกอบสุดท้ายจาก A
- q :=q - 1
- มิฉะนั้น
- ออกมาจากลูป
- M :=สูงสุด M และขนาด A + ขนาด B
- ถ้า arr[p-1] <=arr[p] แล้ว
- ผลตอบแทน 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
