Chương trình tìm độ dài dãy con tăng dần dài nhất trong Python

Cho một danh sách các số. Ta cần tìm độ dài của dãy con tăng dần dài nhất (Longest Increasing Subsequence - LIS).

Ví dụ, với đầu vào [6, 1, 7, 2, 8, 3, 4, 5], kết quả là 5, ứng với dãy con [2, 3, 4, 5, 6].

Giải thuật (O(n log n) với nhị phân)

Sử dụng mảng tails để lưu giá trị cuối nhỏ nhất của các dãy con tăng độ dài i+1:

1. Khởi tạo mảng tails kích thước len(nums) điền 0, và size = 0.
2. Với mỗi phần tử x trong nums:
   • Tìm vị trí i trong tails[0..size-1] bằng tìm kiếm nhị phân sao cho tails[i] >= x (lower bound).
   • Gán tails[i] = x.
   • Nếu i == size, tăng size lên 1.
3. Trả về size.

Ví dụ minh họa

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) // 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

Đầu vào

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

Đầu ra

5