สมมติว่าเรามีอาร์เรย์จำนวนเต็ม A เราต้องหาอาร์เรย์ย่อยที่ต่อเนื่องซึ่งความยาวอย่างน้อยหนึ่ง และมีผลรวมมากที่สุด และคืนค่าผลรวมนั้นด้วย เช่นถ้าอาร์เรย์ A เป็น A = [-2,1,-3,4,-1,2,1,-5,4] ผลรวมจะเป็น 6 และอาร์เรย์ย่อยจะเป็น [4, -1, 2, 1]
ในการแก้ปัญหานี้ เราจะลองใช้แนวทาง Dynamic Programming
- กำหนดอาร์เรย์ dp ขนาดเท่ากับ A และเติมด้วย 0
- dp[0] := A[0]
- สำหรับ 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])
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
