Mảng con lớn nhất trong Python

Cho mảng số nguyên A. Tìm mảng con liên tiếp có tổng lớn nhất (độ dài ≥1). Ví dụ: [-2,1,-3,4,-1,2,1,-5,4] → 6 (mảng con [4,-1,2,1]).

Giải pháp

Quy hoạch động (Kadane):

• dp[0]=A[0].
• dp[i]=max(dp[i-1]+A[i], A[i]).
• Trả về max(dp).

Ví dụ

Triển khai Python:

class Solution(object): 
    def maxSubArray(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.maxSubArray(nums))

Đầu vào

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

Đầu ra

8