โปรแกรมหาผลรวมสับลิสต์ใหญ่สุด K ตัวใน Python

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

ตัวอย่าง: nums = [2, 4, 5, -4], k = 1 ผลลัพธ์ 11 เลือก [2, 4, 5]

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

1. s = ans = lo = 0
2. วน min(k, 2) รอบ:
   • วนแต่ละ x ใน nums:
     • s += x
     • lo = min(lo, s)
     • ans = max(ans, s - lo)
3. คืน ans + max(0, sum(nums)) * max(0, k-2)

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

class Solution:
    def solve(self, nums, k):
        s = ans = lo = 0
        for _ in range(min(k, 2)):
            for x in nums:
                s += x
                lo = min(lo, s)
                ans = max(ans, s - lo)
        return ans + max(0, sum(nums)) * max(0, (k - 2))

ob = Solution()
nums = [2, 4, 5, -4]
k = 1
print(ob.solve(nums, k))

อินพุต

[2, 4, 5, -4], 1

เอาต์พุต

11