โปรแกรมหาความยาวของลำดับย่อยที่เพิ่มขึ้นมากที่สุดใน Python

สมมติว่าเรามีรายการตัวเลข เราต้องการหาความยาวของลำดับย่อยที่เพิ่มขึ้นมากที่สุด (Longest Increasing Subsequence - LIS) ตัวอย่างเช่น หากอินพุตคือ [6, 1, 7, 2, 8, 3, 4, 5] ผลลัพธ์จะเป็น 5 เนื่องจากลำดับย่อยที่เพิ่มขึ้นมากที่สุดคือ [2, 3, 4, 5, 6]

ขั้นตอนการแก้ปัญหา (O(n log n) ด้วย Binary Search)

1. สร้างอาร์เรย์ tails ขนาดเท่ากับ nums และเติมด้วย 0
2. กำหนด size = 0
3. สำหรับแต่ละองค์ประกอบ x ใน nums:
   • กำหนด i = 0, j = size
   • วนลูป while i != j:
     • mid = i + (j - i) // 2
     • หาก tails[mid] < x ให้ i = mid + 1 มิฉะนั้น j = mid
   • tails[i] = x
   • size = max(i + 1, size)
4. คืนค่า size

ตัวอย่างโค้ด Python

class Solution:
    def solve(self, nums):
        tails = [0] * len(nums)
        size = 0
        
        for x in nums:
            i, j = 0, size
            while i != j:
                mid = i + (j - i) // 2
                if tails[mid] < x:
                    i = mid + 1
                else:
                    j = mid
            tails[i] = x
            size = max(i + 1, size)
        
        return size

ob = Solution()
nums = [7, 2, 8, 3, 9, 4, 5, 6]
print(ob.solve(nums))  # Output: 5

อินพุต

[7, 2, 8, 3, 9, 4, 5, 6]

เอาต์พุต

5