Chương trình tìm tổng dãy con lớn nhất chia hết cho k trong Python

Cho mảng số không âm và k dương. Tìm tổng lớn nhất của dãy con (subsequence) chia hết cho k.

Ví dụ: nums=[4,6,8,2], k=2 → 20 (tổng cả mảng).

Giải thuật (Tổng toàn bộ - loại bỏ dãy con nhỏ nhất dư đúng số)

1. Tính total = sum(nums), rem = total % k.
2. Nếu rem == 0 → trả về total.
3. Sắp xếp nums. Duyệt tất cả tổ hợp con (từ nhỏ đến lớn), tìm tổ hợp đầu tiên có sum % k == rem. Trả về total - sum(tổ_hợp).

Lưu ý: Duyệt tất cả tổ hợp O(2^n) chỉ phù hợp n nhỏ. Với n lớn cần DP modulo.

Ví dụ minh họa

from itertools import chain, combinations

class Solution:
    def solve(self, nums, k):
        total = sum(nums)
        rem = total % k
        if rem == 0:
            return total
        nums.sort()
        for r in range(1, len(nums) + 1):
            for combo in combinations(nums, r):
                if sum(combo) % k == rem:
                    return total - sum(combo)
        return 0

ob = Solution()
print(ob.solve([4, 6, 8, 2], 2))  # Output: 20

Đầu vào / Đầu ra

Input: [4, 6, 8, 2], 2

Output: 20