Chương trình tìm độ dài dãy con tăng dần dài nhất có ít nhất k phần tử lẻ trong Python

Cho danh sách nums và số k. Tìm độ dài dãy con tăng dần (LIS) dài nhất chứa ít nhất k số lẻ.

Ví dụ: nums = [12, 14, 16, 5, 7, 8], k = 2 → kết quả 3 (dãy [5, 7, 8]).

Giải thuật (Backtracking / DFS với tỉa nhánh)

Hàm dp(i, j, odd, taken): đang xét từ chỉ số i, tiếp theo từ j, đã có odd số lẻ, độ dài taken.

• Nếu odd >= k: cập nhật best.
• Nếu j == len(nums): dừng.
• Nếu nums[j] > nums[i]: chọn j → dp(j, j+1, odd + (nums[j]&1), taken+1).
• Bỏ qua j: dp(i, j+1, odd, taken).

Khởi tạo: chạy dp(i, i+1, nums[i]&1, 1) cho mọi i.

Ví dụ minh họa

class Solution:
    def solve(self, nums, k):
        best = 0
        def dp(i, j, odd, taken):
            nonlocal best
            if odd >= k:
                best = max(best, taken)
            if j == len(nums):
                return
            if nums[j] > nums[i]:
                dp(j, j + 1, odd + (nums[j] & 1), taken + 1)
            dp(i, j + 1, odd, taken)
        
        for i in range(len(nums)):
            dp(i, i + 1, nums[i] & 1, 1)
        return best

ob = Solution()
nums = [12, 14, 16, 5, 7, 8]
k = 2
print(ob.solve(nums, k))  # Output: 3

Đầu vào / Đầu ra

Input: [12, 14, 16, 5, 7, 8], 2

Output: 3