Chương trình tìm tổng dãy con liên tiếp lớn nhất trong Python

Cho mảng A, tìm dãy con liên tiếp (subarray) có tổng lớn nhất và trả về tổng đó (Kadane's Algorithm).

Ví dụ: A = [-2,1,-3,4,-1,2,1,-5,4] → tổng max = 6 (dãy [4, -1, 2, 1]).

Giải thuật (Dynamic Programming - Kadane)

1. Khởi tạo mảng cùng kích thước , .
2. Với từ 1 đến : .
3. Trả về .

Có thể tối ưu không gian O(1) bằng 2 biến.

Ví dụ minh họa

class Solution:
    def solve(self, nums):
        dp = [0] * 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))  # Output: 8

Đầu vào

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

Đầu ra

8