โปรแกรมหาผลรวมสูงสุดของรายการย่อยวงกลมใน Python

สมมติว่าเรามีรายการตัวเลข nums พิจารณาว่าเป็นรายการวงกลม (start และ end เป็นเพื่อนบ้าน) เราต้องการหาผลรวมสูงสุดของรายการย่อยที่ไม่ว่างในรายการวงกลม

ตัวอย่างเช่น หาก nums = [2, 3, -7, 4, 5] ผลลัพธ์จะเป็น 14 เนื่องจากเลือก [4, 5, 2, 3] ผลรวม = 14

ขั้นตอนการแก้ปัญหา (Kadane's Algorithm แบบขยาย)

1. max_sum = -inf, cur_max = 0
2. min_sum = +inf, cur_min = 0
3. สำหรับแต่ละ num ใน nums:
   • cur_max = max(num, cur_max + num)
   • max_sum = max(max_sum, cur_max)
   • cur_min = min(num, cur_min + num)
   • min_sum = min(min_sum, cur_min)
4. หาก max_sum <= 0 ให้คืนค่า max_sum (ทุกตัวเป็นลบ)
5. มิฉะนั้น คืนค่า max(max_sum, sum(nums) - min_sum)

หลักการ: ผลรวมวงกลมสูงสุด = max(ปกติ, ผลรวมทั้งหมด - ผลรวมต่ำสุด)

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

import math

class Solution:
    def solve(self, nums):
        max_sum = -math.inf
        cur_max = 0
        min_sum = math.inf
        cur_min = 0
        
        for num in nums:
            cur_max = max(num, cur_max + num)
            max_sum = max(max_sum, cur_max)
            cur_min = min(num, cur_min + num)
            min_sum = min(min_sum, cur_min)
        
        if max_sum <= 0:
            return max_sum
        
        return max(max_sum, sum(nums) - min_sum)

ob = Solution()
nums = [2, 3, -7, 4, 5]
print(ob.solve(nums))  # Output: 14

อินพุต

[2, 3, -7, 4, 5]

เอาต์พุต

14