Chương trình tìm kích thước tập con lớn nhất mà mọi cặp một số chia hết số kia trong Python

Cho danh sách số duy nhất nums. Tìm tập con lớn nhất sao cho với mọi cặp (i, j) trong tập con, hoặc i % j == 0 hoặc j % i == 0.

Ví dụ: nums = [3,6,12,24,26,39] → tập con [3,6,12,24] kích thước 4.

Giải thuật (DP trên mảng đã sắp xếp)

• Sắp xếp nums.
• dp[i] = kích thước tập con lớn nhất kết thúc tại i (chứa nums[i]).
• Khởi tạo dp[i] = 1.
• Duyệt i từ 1 đến n-1, j từ 0 đến i-1:
  • Nếu nums[i] % nums[j] == 0: dp[i] = max(dp[i], dp[j] + 1).
• Kết quả = max(dp).

Mã nguồn Python

class Solution:
    def solve(self, nums):
        dp = [1] * len(nums)
        nums.sort()
        n = len(nums)
        if n <= 1:
            return n
        ans = 0
        for i in range(1, n):
            for j in range(i):
                if nums[i] % nums[j] == 0:
                    dp[i] = max(dp[i], dp[j] + 1)
            ans = max(ans, dp[i])
        return ans

ob = Solution()
nums = [3, 6, 12, 24, 26, 39]
print(ob.solve(nums))  # Output: 4

Đầu vào

[3, 6, 12, 24, 26, 39]

Đầu ra

4