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

สมมติว่ามีรายการตัวเลข nums และค่า x, y ต้องการหาผลรวมสูงสุดของสองสับลิสต์ไม่ทับซ้อนที่มีความยาว x และ y

ตัวอย่าง: nums = [3, 2, 10, -2, 7, 6], x = 3, y = 1 ผลลัพธ์คือ 22 เลือก [3, 2, 10] (ความยาว 3) และ [7] (ความยาว 1)

ขั้นตอนการแก้ปัญหา

1. สร้าง prefix sum P เริ่มจาก 0
2. ฟังก์ชัน solve(len1, len2):
   • Q[i] = P[i+len1] - P[i] (ผลรวมทุก subarray ความยาว len1)
   • prefix = prefix max ของ Q
   • วน i จาก len1 ถึง len(P)-len2:
     • left = prefix[i-len1]
     • right = P[i+len2] - P[i]
     • ans = max(ans, left + right)
   • คืน ans
3. คืน max(solve(len1, len2), solve(len2, len1))

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

class Solution:
    def solve(self, A, len1, len2):
        P = [0]
        for x in A:
            P.append(P[-1] + x)
        def solve(len1, len2):
            Q = [P[i + len1] - P[i] for i in range(len(P) - len1)]
            prefix = Q[:]
            for i in range(len(prefix) - 1):
                prefix[i + 1] = max(prefix[i + 1], prefix[i])
            ans = float("-inf")
            for i in range(len1, len(P) - len2):
                left = prefix[i - len1]
                right = P[i + len2] - P[i]
                ans = max(ans, left + right)
            return ans
        return max(solve(len1, len2), solve(len2, len1))

ob = Solution()
nums = [3, 2, 10, -2, 7, 6]
x = 3
y = 1
print(ob.solve(nums, x, y))

อินพุต

[3, 2, 10, -2, 7, 6], 3, 1

เอาต์พุต

22