Mảng con tối đa trong Python

Giả sử chúng ta có một mảng số nguyên A. Chúng ta phải tìm các mảng con liền nhau có độ dài ít nhất là một và có tổng lớn nhất, đồng thời trả về tổng của nó. Vì vậy, nếu mảng A giống như A =[-2,1, -3,4, -1,2,1, -5,4], thì tổng sẽ là 6. Và mảng con sẽ là [4, -1 , 2, 1]

Để giải quyết vấn đề này, chúng tôi sẽ cố gắng sử dụng cách tiếp cận Lập trình động.

• xác định một mảng dp giống với kích thước của A và điền nó bằng 0
• dp [0]:=A [0]
• cho i =1 với kích thước là A - 1
  • dp [i]:=tối đa của dp [i - 1] + A [i] và A [i]
• trả về giá trị tối đa tính bằng dp

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

Ví dụ (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))

Đầu vào

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

Đầu ra

8