โปรแกรมค้นหา k รายการย่อยที่มีผลรวมมากที่สุดและส่งคืนผลรวมในลำดับจากน้อยไปมากใน Python

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และอีกค่าหนึ่งคือ k เราต้องหารายการย่อย k ที่มีผลรวมมากที่สุดและส่งคืนผลรวมในลำดับที่ไม่ลดลง

ดังนั้นหากอินพุตเป็น nums =[2, 4, 5, -100, 12, -30, 6, -2, 6] k =3 ผลลัพธ์จะเป็น [10, 11, 12] ตามที่เรา มี 3 รายการย่อยที่มีผลรวมมากที่สุด − [6, -2, 6], [2, 4, 5], [12].

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

• ps :=รายการ 1 + ขนาดของ nums และเติมด้วย 0
• สำหรับแต่ละดัชนี i และค่า v nums ทำ
  • ps[i + 1] :=v + ps[i]
• hp :=รายการใหม่
• สำหรับฉันในช่วง 0 ถึงขนาดของ ps ทำ
  • สำหรับ j ในช่วง i + 1 ถึงขนาดของ ps ทำ
    • แทรก -(ps[j] - ps[i]) ลงใน ps heap
• res :=เปิดองค์ประกอบทั้งหมดใน ps heap แล้วย้อนกลับ
• ผลตอบแทน

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

from heapq import heappop, heappush
class Solution:
   def solve(self, nums, k):
      ps = [0 for _ in range(len(nums) + 1)]
      for i, v in enumerate(nums):
         ps[i + 1] = v + ps[i]
      hp = []
      for i in range(len(ps)):
         for j in range(i + 1, len(ps)):
            heappush(hp, -(ps[j] - ps[i]))
            return list(reversed([-heappop(hp)
      for _ in range(k)]))
ob = Solution()
nums = [2, 4, 5, -100, 12, -30, 6, -2, 6] k = 3
print(ob.solve(nums, k))

อินพุต

[2, 4, 5, -100, 12, -30, 6, -2, 6],3

ผลลัพธ์

[10, 11, 12]