Chương trình tìm ra tổng chuỗi con chia K lớn nhất trong Python

Giả sử chúng ta được cung cấp một danh sách các số không âm và giá trị dương k. Chúng ta phải tìm dãy con có tổng lớn nhất sao cho tổng chia hết cho k.

Vì vậy, nếu đầu vào là nums =[4, 6, 8, 2], k =2, thì đầu ra sẽ là 20.

Tổng của cả mảng là 20 chia hết cho 2.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• numsSum:=tổng các giá trị trong nums danh sách đầu vào

• phần còn lại:=numsSum mod k

• nếu phần còn lại bằng 0 thì

  • trả về numsSum

• sắp xếp số lượng danh sách

• cho mỗi tổ hợp số tpl tính bằng nums. làm

  • subSeqSum:=sum (tpl)

  • nếu subSeqSum mod k giống với phần còn lại, thì

    • trả về numsSum - subSeqSum

• trả về 0

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

[4, 6, 8, 2], 2

Đầu ra

20