โปรแกรมค้นหาผลรวมย่อย K-Divisible ที่ใหญ่ที่สุดใน Python

สมมติว่าเราได้รับรายการตัวเลขที่ไม่เป็นลบ และค่าบวก k เราต้องหาผลรวมสูงสุดของตัวเลขที่ผลรวมหารด้วย k ลงตัว

ดังนั้น หากอินพุตเป็นแบบ nums =[4, 6, 8, 2], k =2 ผลลัพธ์จะเป็น 20

ผลรวมของอาร์เรย์ทั้งหมดคือ 20 ซึ่งหารด้วย 2 ลงตัว

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• numsSum :=ผลรวมของค่าในรายการอินพุต nums

• ส่วนที่เหลือ :=numsSum mod k

• หากเศษเหลือเท่ากับ 0 แล้ว

  • ส่งคืน numsSum

• เรียงเลขรายการ

• สำหรับการรวมกันแต่ละหมายเลข tpl ใน nums ทำ

  • 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