Pythonで最大のK分割可能な部分列の合計を見つけるプログラム

したがって、入力がnums =[4、6、8、2]、k =2の場合、出力は20になります。

配列全体の合計は20で、2で割り切れます。

これを解決するには、次の手順に従います-

• numsSum：=入力リストnumsの値の合計

• 余り：=numsSum mod k

• 余りが0と同じ場合、

  • numsSumを返す

• リスト番号を並べ替える

• 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