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

ปัญหา

อาร์เรย์ nums และ k หาลำดับย่อย (subsequence) ขนาด k ที่ "competitive" มากที่สุด คือ ตำแหน่งแรกที่ต่างกัน ตัวเลขน้อยกว่า

ตัวอย่าง

nums=[4,6,3,7], k=2 → [3,7] (subsequences: [4,6],[4,3],[4,7],[6,3],[6,7],[3,7] → [3,7] น้อยที่สุด)

ขั้นตอนการแก้ปัญหา

1. attempts := len(nums) - k
2. stack := []
3. สำหรับ num ใน nums:
   • بينما stack and num < stack[-1] and attempts > 0: stack.pop(); attempts -= 1
   • stack.append(num)
4. คืน stack[:k]

การนำไปใช้งาน (Python)

def solve(nums, k):
    attempts = len(nums) - k
    stack = []
    for num in nums:
        while stack and num < stack[-1] and attempts > 0:
            stack.pop()
            attempts -= 1
        stack.append(num)
    return stack[:k]

nums = [4,6,3,7]
k = 2
print(solve(nums, k))

อินพุต

[4,6,3,7], 2

เอาต์พุต

[3,7]