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 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告