สมมติว่าเรามีอาร์เรย์ A เราต้องหารายการย่อยที่อยู่ติดกันซึ่งมีค่าสูงสุดและส่งคืนผลรวมด้วย ดังนั้นหากอาร์เรย์ A เหมือนกับ A =[-2,1,-3,4,-1,2,1,-5,4] ผลรวมจะเป็น 6 และอาร์เรย์ย่อยจะเป็น [4, -1, 2, 1].
เพื่อแก้ปัญหานี้ เราจะพยายามใช้วิธีการเขียนโปรแกรมแบบไดนามิก
-
กำหนดอาร์เรย์ dp เท่ากับขนาด A และเติมด้วย 0
-
dp[0] :=A[0]
-
สำหรับ i :=1 ถึงขนาด A – 1
-
dp[i] :=สูงสุดของ dp[i – 1] + A[i] และ A[i]
-
-
ผลตอบแทนสูงสุดใน dp
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution(object): def solve(self, nums): dp = [0 for i in range(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))
อินพุต
[-2,1,-3,7,-2,2,1,-5,4]
ผลลัพธ์
8
