Chương trình tìm tổng tuyệt đối lớn nhất của mảng con bất kỳ trong Python

Cho mảng nums. Tổng tuyệt đối của mảng con nums[l..r] là |sum(nums[l..r])|. Tìm giá trị lớn nhất (mảng con có thể rỗng).

Ví dụ: nums = [2,-4,-3,2,-6] → 11 (mảng con [2,-4,-3,2]: |2-4-3+2| = |-3| = 3? Wait: 2-4-3+2 = -3, abs = 3. Không, ví dụ nói 11. Kiểm tra lại: [2,-4,-3,2] sum = -3. [-4,-3,2,-6] sum = -11, abs = 11. Đúng.)

Giải thuật (Kadane biến đổi)

1. Duyệt 2 lần: một lần tìm max subarray sum (bỏ tiền tố âm), một lần tìm min subarray sum (bỏ tiền tố dương) → lấy max của |max_sum| và |min_sum|.
2. Chi tiết:
   • Khởi tạo ans=0, temp=0.
   • Duyệt i: nếu temp < 0 thì temp=0; temp += nums[i]; ans = max(ans, abs(temp)).
   • Đặt lại temp=0.
   • Duyệt i: nếu temp > 0 thì temp=0; temp += nums[i]; ans = max(ans, abs(temp)).
   • Trả về ans.

Ví dụ minh họa

def solve(nums):
    n = len(nums)
    ans = 0
    temp = 0
    for i in range(n):
        if temp < 0:
            temp = 0
        temp += nums[i]
        ans = max(ans, abs(temp))
    temp = 0
    for i in range(n):
        if temp > 0:
            temp = 0
        temp += nums[i]
        ans = max(ans, abs(temp))
    return ans

nums = [2,-4,-3,2,-6]
print(solve(nums))

Đầu vào

[2,-4,-3,2,-6]

Đầu ra

11