Chương trình tìm tổng của danh sách con liền kề với tổng tối đa bằng Python

Giả sử chúng ta có một mảng A. Chúng ta phải tìm danh sách con liền kề có giá trị lớn nhất và cũng 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 phương pháp 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]

• for i:=1 to size of A - 1

  • dp [i]:=tối đa của dp [i - 1] + A [i] và A [i]

• trả về tối đa trong dp

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

Ví dụ

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))

Đầu vào

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

Đầu ra

8