โปรแกรมหาผลรวมสูงสุดจากการ Pop K องค์ประกอบจากหลาย Stack ใน Python

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

ตัวอย่างเช่น stacks = [[50, -4, -15], [2], [6, 7, 8]], k = 4 ผลลัพธ์คือ 39 (pop ทั้ง 3 ตัวจาก stack แรก และ 1 ตัวจาก stack สุดท้าย: -15 + -4 + 50 + 8 = 39)

ขั้นตอนการแก้ปัญหา (Recursive + Memoization)

1. ฟังก์ชัน rec(i, n): ผลรวมสูงสุดจาก stack ที่ i เป็นต้นไป เมื่อ pop ไปแล้ว n ตัว
   • Base cases: n == k คืน 0; k หรือ i == len(stacks) คืน -inf
   • หากเป็น stack สุดท้าย: ตรวจสอบว่า pop ได้ครบ k-n ตัวหรือไม่
   • ลอง pop 0 ถึง ทั้ง stack i คำนวณผลรวม + rec(i+1, n+popped)
   • คืนค่า max ของทุกกรณี
2. เรียก rec(0, 0)

ตัวอย่างโค้ด Python

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
                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))  # Output: 39

อินพุต

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

เอาต์พุต

39