โปรแกรมหาผลรวมมากที่สุดของ 3 สับลิสต์ไม่ทับซ้อนขนาดเท่ากันใน Python

สมมติว่าเรามีรายการตัวเลข nums และค่า k เราต้องการหาผลรวมมากที่สุดของ 3 สับลิสต์ (sublists) ที่ไม่ทับซ้อนกัน (non-overlapping) แต่ละตัวมีขนาด k

เช่น ถ้าข้อมูลนำเข้าคือ nums = [2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3] k = 3 ผลลัพธ์จะเป็น 27 เนื่องจากเลือกได้ [2, 2, 2], [4, 4, 4], [3, 3, 3] ผลรวมรวม = 27

ขั้นตอนการแก้ปัญหา (Prefix Sum + Sliding Window Max)

• สร้าง P = prefix sum array (เริ่มต้นที่ 0)
• Q[i] = P[i+K] - P[i] = ผลรวมของสับลิสต์ขนาด K เริ่มที่ i
• สร้าง prefix และ suffix array จาก Q โดย:
  • prefix[i+1] = max(prefix[i+1], prefix[i]) (ค่าสูงสุดทางซ้าย)
  • suffix[~(i+1)] = max(suffix[~(i+1)], suffix[~i]) (ค่าสูงสุดทางขวา)
• คำตอบ = max(Q[i] + prefix[i-K] + suffix[i+K]) สำหรับ i = K .. len(Q)-K-1

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

class Solution:
    def solve(self, A, K):
        P = [0]
        for x in A:
            P.append(P[-1] + x)
        Q = [P[i + K] - P[i] for i in range(len(P) - K)]
        prefix = Q[:]
        suffix = Q[:]
        for i in range(len(Q) - 1):
            prefix[i + 1] = max(prefix[i + 1], prefix[i])
            suffix[~(i + 1)] = max(suffix[~(i + 1)], suffix[~i])
        return max(Q[i] + prefix[i - K] + suffix[i + K] for i in range(K, len(Q) - K))

ob = Solution()
nums = [2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3]
k = 3
print(ob.solve(nums, k))

ข้อมูลนำเข้า

[2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3], 3

ผลลัพธ์

27