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

Cho danh sách số nums, tìm độ dài dãy con tăng dần dài nhất (LIS), giả định dãy con có thể "quay vòng" về đầu danh sách (circular).

Ví dụ: nums=[6,5,8,2,3,4] → output 5 (LIS vòng tròn: [2,3,4,6,8]).

Ý tưởng: Nối mảng với chính nó a = nums + nums. Với mỗi vị trí bắt đầu i trong n phần tử đầu, tìm LIS trên đoạn a[i : i+n] (độ dài n). Max của tất cả là đáp án.

Thuật toán LIS O(n log n) với binary search:

Duy trì mảng dp lưu giá trị cuối nhỏ nhất của dãy con tăng độ dài len
Với mỗi n: tìm vị trí k = bisect_left(dp, n)
Nếu k == len(dp): dp.append(n)
Ngược lại: dp[k] = n
len(dp) = độ dài LIS hiện tại

Triển khai

import bisect

class Solution:
    def solve(self, nums):
        a = nums + nums
        ans = 0
        for i in range(len(nums)):
            dp = []
            for j in range(i, len(nums) + i):
                n = a[j]
                k = bisect.bisect_left(dp, n)
                if k == len(dp):
                    dp.append(n)
                else:
                    dp[k] = n
                ans = max(ans, len(dp))
        return ans

ob = Solution()
nums = [4, 5, 8, 2, 3, 4]
print(ob.solve(nums))

Đầu vào

[4, 5, 8, 2, 3, 4]

Đầu ra

Phân tích: Phức tạp O(n² log n). Có thể tối ưu bằng Segment Tree / Fenwick Tree trên giá trị nén (coordinate compression) về O(n log n) tổng, nhưng phức tạp hơn. Với n ≤ 1000, O(n² log n) chấp nhận được.