Python程序：查找最大K可整除子序列和

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

因此，如果输入类似于 nums = [4, 6, 8, 2]，k = 2，则输出将为 20。

整个数组的和是 20，可以被 2 整除。

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

  • numsSum := 输入列表 nums 中值的总和

  • remainder := numsSum mod k

  • 如果余数与 0 相同，则

    • 返回 numsSum

  • 对列表 nums 进行排序

  • 对于 nums 中的每个数字组合 tpl

    • subSeqSum := sum(tpl)

    • 如果 subSeqSum mod k 与余数相同，则

      • 返回 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

更新于：2020年12月15日

344 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告