LeetCode #300 LIS: จาก DP ตารางตรงไปตรงมาถึง patience sorting และ Fenwick tree

Longest Increasing Subsequence ให้หาความยาว subsequence ที่ค่าเพิ่มขึ้นแบบ strictly increasing สมาชิกไม่ต้องติดกัน แต่ต้องรักษาลำดับเดิม ตัวอย่าง [10, 9, 2, 5, 3, 7, 101, 18] ตอบ 4 จากเส้นทางอย่าง [2, 3, 7, 18] คำว่า strict สำคัญ: ค่าเท่ากันต่อกันไม่ได้ครับ

วิธี 1: Dynamic programming O(n²)

กำหนด dp[i] เป็น LIS ที่จบตรงตำแหน่ง i แล้วมองทุก j < i ที่ nums[j] < nums[i] สูตรตรงกับนิยามและย้อนสร้างคำตอบจริงได้ง่ายหากเก็บ parent เพิ่ม เหมาะกับการอธิบายครั้งแรกหรือ n ไม่ใหญ่

วิธี 2: Patience sorting + binary search

เก็บ tails[k] เป็นปลายที่เล็กที่สุดของ subsequence ความยาว k+1 สำหรับแต่ละค่า ใช้ bisect_left หา pile แรกที่ไม่น้อยกว่าค่านั้นแล้วแทนที่ ความยาว tails คือคำตอบ เวลา O(n log n) พื้นที่ O(n) และเป็นคำตอบแนะนำของโจทย์นี้ แต่ tails ไม่จำเป็นต้องเป็น subsequence จริงทั้งชุด

วิธี 3: Fenwick tree หลังบีบพิกัด

บีบค่าตัวเลขเป็น rank แล้ว query LIS สูงสุดของ rank ที่เล็กกว่าค่าปัจจุบัน จากนั้น update rank ปัจจุบัน วิธีนี้ O(n log n) เช่นกันและต่อยอดเป็นงาน prefix maximum/counting ได้ดี แต่โค้ดยาวกว่า patience sorting

from bisect import bisect_left
import unittest


def lis_dp(nums: list[int]) -> int:
    if not nums:
        return 0
    dp = [1] * len(nums)
    for right in range(len(nums)):
        for left in range(right):
            if nums[left] < nums[right]:
                dp[right] = max(dp[right], dp[left] + 1)
    return max(dp)


def lis_patience(nums: list[int]) -> int:
    tails: list[int] = []
    for value in nums:
        index = bisect_left(tails, value)
        if index == len(tails):
            tails.append(value)
        else:
            tails[index] = value
    return len(tails)


def lis_fenwick(nums: list[int]) -> int:
    ranks = {value: index + 1 for index, value in enumerate(sorted(set(nums)))}
    tree = [0] * (len(ranks) + 1)

    def query(index: int) -> int:
        best = 0
        while index > 0:
            best = max(best, tree[index])
            index -= index & -index
        return best

    for value in nums:
        index = ranks[value]
        best = query(index - 1) + 1
        cursor = index
        while cursor < len(tree):
            tree[cursor] = max(tree[cursor], best)
            cursor += cursor & -cursor
    return query(len(ranks))


class LISTests(unittest.TestCase):
    def test_all_methods(self):
        cases = [
            ([10, 9, 2, 5, 3, 7, 101, 18], 4),
            ([0, 1, 0, 3, 2, 3], 4),
            ([7, 7, 7, 7], 1),
            ([], 0),
        ]
        for solve in (lis_dp, lis_patience, lis_fenwick):
            for nums, expected in cases:
                self.assertEqual(solve(nums), expected)


if __name__ == "__main__":
    unittest.main()

Decision table

วิธี	เวลา	พื้นที่	คืน sequence จริง	เหมาะกับ
DP	O(n²)	O(n)	เพิ่ม parent ได้ตรงไปตรงมา	สอนแนวคิด, input เล็ก
Patience	O(n log n)	O(n)	ต้องเก็บ predecessor เพิ่ม	คำตอบ default สำหรับ length
Fenwick	O(n log n)	O(n)	ต้องเพิ่ม metadata	query/update ตามช่วงหรือ variant ซับซ้อน

Edge cases และกับดัก

ค่าเท่ากันต้องไม่เพิ่มความยาว จึงใช้ bisect_left ไม่ใช่ bisect_right และ Fenwick ต้อง query ถึง rank - 1 เท่านั้น เทสต์ array ว่าง, ค่าเดียว, ลดลงล้วน, ซ้ำล้วน และมีค่าติดลบ สำหรับ DP อย่าลืมจัดการ input ว่างก่อน max(dp)

ถ้าโจทย์ขอ subsequence จริง ไม่ใช่แค่ความยาว ให้เก็บ predecessor กับ index ปลายของแต่ละความยาวในวิธี patience อย่าคืน tails ตรง ๆ เพราะค่าที่ถูกแทนภายหลังอาจมาจากคนละเส้นทาง ในการสัมภาษณ์เริ่ม DP เพื่อสร้าง recurrence แล้ว optimize เป็น patience sorting จะอธิบายเหตุผลได้ดีกว่าท่อง binary search มาเลย

Recap

• DP ทำให้ recurrence ชัด แต่โตเป็นกำลังสอง
• patience sorting เป็น default สำหรับความยาว O(n log n)
• strict increasing ต้องใช้ตำแหน่งแรกที่ >= value
• Fenwick tree คุ้มเมื่อโจทย์ต่อยอดเป็น prefix query หรือการนับครับ