在Python中查找最大的可被K整除的子序列和的程序

假设我们有一个非负数的列表，以及一个正值k。我们必须找到最大的子序列数字之和，使其可被k整除。

因此，如果输入为nums = [4，6，8，2]，k = 2，那么输出将是20。

整个数组的总和为20，可被2整除。

为了解决这个问题，我们将遵循以下步骤 –

• numsSum：获取输入列表nums中的值的总和

• remainder：numsSum mod k

• 如果remainder与0相同，则

  • 返回numsSum
• 对nums列表进行排序

• 对于nums中的每个数字组合tpl。做以下操作

  • subSeqSum：sum（tpl）

  • 如果subSeqSum mod k与remainder相同，则

    • 返回numsSum-subSeqSum
• 返回0

请看以下实现以获得更好的理解

例子

from itertools import chain, combinations
class Solution:
   def solve(self, nums, k):
      numsSum = sum(nums)
      remainder = numsSum % k
      if remainder == 0:
         return numsSum
      nums.sort()
      for tpl in chain.from_iterable(combinations(nums, r) for r in range(1, len(nums) + 1)):
         subSeqSum = sum(tpl)
         if subSeqSum % k == remainder:
            return numsSum - subSeqSum
      return 0
ob1 = Solution()
print(ob1.solve([4, 6, 8, 2], 2))

输入

[4, 6, 8, 2]，2

输出

20