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

สมมติว่าเรามีอาร์เรย์ A เราต้องการหารายการย่อยติดกัน (contiguous sublist) ที่มีผลรวมสูงสุด และคืนค่าผลรวมนั้น (Kadane's Algorithm)

ตัวอย่างเช่น A = [-2, 1, -3, 4, -1, 2, 1, -5, 4] ผลรวมสูงสุดคือ 6 จาก subarray [4, -1, 2, 1]

ขั้นตอนการแก้ปัญหา (Dynamic Programming - Kadane's Algorithm)

1. สร้างอาร์เรย์ dp ขนาดเท่า A เติม 0
2. dp[0] = A[0]
3. สำหรับ i จาก 1 ถึง len(A) - 1:
   • dp[i] = max(dp[i-1] + A[i], A[i])
4. คืนค่า max(dp)

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

class Solution:
    def solve(self, nums):
        dp = [0] * len(nums)
        dp[0] = nums[0]
        
        for i in range(1, len(nums)):
            dp[i] = max(dp[i-1] + nums[i], nums[i])
        
        return max(dp)

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

อินพุต

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

เอาต์พุต

8