โปรแกรมค้นหาผลรวมสูงสุดขององค์ประกอบ k ที่แตกจากรายการสแต็คใน Python

สมมติว่าเรามีรายการสแต็คและจำนวนเต็ม k เราต้องหาผลรวมสูงสุดที่เป็นไปได้จากการดึงองค์ประกอบ k ออกจากการรวมกองใดๆ

ดังนั้นหากอินพุตเป็นเหมือน stacks =[[50, -4, -15],[2],[6, 7, 8]], k =4 ผลลัพธ์จะเป็น 39 เนื่องจากเราสามารถเปิดได้ทั้งหมด 3 องค์ประกอบจากสแต็กแรกและเปิดองค์ประกอบสุดท้ายของสแต็กสุดท้ายเพื่อรับ -15 + -4 + 50 + 8 =39

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

กำหนดฟังก์ชัน rec() นี่จะใช้เวลา i, n
ถ้า n เหมือนกับ k แล้ว
- คืนค่า 0
ถ้า n> k แล้ว
- คืนค่าอินฟินิตี้เชิงลบ
ถ้าฉันเหมือนกับ count of stacks แล้ว
- คืนค่าอินฟินิตี้เชิงลบ
ถ้าฉันเหมือนกับการนับกอง - 1 แล้ว
- จำเป็น :=k - n
- ถ้าจำเป็น> จำนวนองค์ประกอบของ stacks[i] แล้ว
  - คืนค่าอินฟินิตี้เชิงลบ
- มิฉะนั้น
  - ส่งคืนผลรวมขององค์ประกอบของ stack[i] จำนวนองค์ประกอบที่ต้องการล่าสุด
res :=-math.inf, su :=0
สำหรับขนาดช่วงของสแต็ค[i] - 1 ถึง 0,
ลดลง 1 ทำ
- su :=su + stacks[i, sti]
- localres :=su + rec(i + 1, n + size of stacks[i] - sti)
- res :=สูงสุดของ res และ localres
คืนค่าสูงสุดของ res และ rec(i + 1, n)
จากเมธอดหลัก เรียก rec(0, 0)

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

ตัวอย่าง

import math

class Solution:
   def solve(self, stacks, k):
      def rec(i, n):
         if n == k:
            return 0
         if n > k:
            return -math.inf
         if i == len(stacks):
            return -math.inf
         if i == len(stacks) - 1:
            needed = k - n
            if needed > len(stacks[i]):
               return -math.inf
            else:
               return sum(stacks[i][-needed:])
         res, su = -math.inf, 0
         for sti in range(len(stacks[i]) - 1, -1, -1):
            su += stacks[i][sti]
            localres = su + rec(i + 1, n + len(stacks[i]) - sti)
            res = max(res, localres)
         return max(res, rec(i + 1, n))

      return rec(0, 0)

ob = Solution()
stacks = [
   [50, -4, -15],
   [2],
   [6, 7, 8]
]
k = 4
print(ob.solve(stacks, k))

อินพุต

[[50, -4, -15],[2],[6, 7, 8]], 4