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