Longest Increasing Subsequence (LIS) ใน Python

หาความยาวของ longest increasing subsequence (ไม่จำเป็นติดกัน) ในอาร์เรย์

ตัวอย่าง

Input: [10,9,2,5,3,7,101,18]
Output: 4  # LIS คือ [2,3,7,101]

อัลกอริทึม Patience Sorting (O(n log n))

1. สร้างอาร์เรย์ tails เก็บค่าสุดท้ายของ subsequence แต่ละความยาว
2. สำหรับแต่ละตัวเลข x:
   • Binary search หาตำแหน่งแรกใน tails ที่ ≥ x
   • แทนที่ค่าที่ตำแหน่งนั้น (หรือ append ถ้ามากกว่าทุกตัว)
3. ขนาดของ tails ที่เต็ม = ความยาว LIS

โค้ด

import bisect

class Solution:
    def lengthOfLIS(self, nums):
        tails = []
        for x in nums:
            idx = bisect.bisect_left(tails, x)
            if idx == len(tails):
                tails.append(x)
            else:
                tails[idx] = x
        return len(tails)

# ทดสอบ
sol = Solution()
print(sol.lengthOfLIS([10,9,2,5,3,7,101,18]))  # 4

หมายเหตุ

• ใช้ bisect_left จากไลบรารีมาตรฐาน
• ถ้าต้องการคืนค่า subsequence จริง ต้องเก็บ predecessor pointers เพิ่ม

สรุป

Binary search + tails array ให้ O(n log n) ดีกว่า DP แบบ O(n²)