파이썬에서 가장 큰 K-분할 수열 합을 찾는 프로그램

음수가 아닌 숫자 목록과 양수 값 k가 주어진다고 가정합니다. 합이 k로 나누어지는 수의 최대 합 부분열을 찾아야 합니다.

따라서 입력이 nums =[4, 6, 8, 2], k =2와 같으면 출력은 20이 됩니다.

전체 배열의 합은 20이며 2로 나눌 수 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• numsSum :=입력 목록 nums의 값 합계

• 나머지 :=numsSum mod k

• 나머지가 0과 같으면

  • numsSum 반환

• 목록 번호 정렬

• 숫자의 각 숫자 조합 tpl에 대해. 하세요

  • subSeqSum :=합계(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