Chương trình tìm tổng mảng con tối đa sau một phép toán bình phương trong Python

Mô tả bài toán

Cho mảng số nguyên. Có thể thực hiện tối đa một phép: chọn một phần tử và thay bằng bình phương của nó. Tìm tổng mảng con lớn nhất có thể đạt được (mảng con không rỗng).

Ví dụ

array = [4, 1, -2, -1] -> bình phương 4 thành 16 -> mảng [16, 1, -2, -1] -> mảng con max [16, 1] tổng = 17.

Giải thuật (Quy hoạch động)

1. dp1[i]: tổng mảng con max kết thúc tại i chưa dùng phép bình phương.
2. dp2[i]: tổng mảng con max kết thúc tại i đã dùng phép bình phương.
3. Cập nhật:
   • dp1[i] = max(dp1[i-1] + num, num)
   • dp2[i] = max(dp1[i-1] + num^2, num^2, dp2[i-1] + num)
4. Kết quả là max(dp2).

Triển khai Python

def solve(array):
    dp1 = [float('-inf')]
    dp2 = [float('-inf')]
    for num in array:
        dp1.append(max(dp1[-1] + num, num))
        dp2.append(max(dp1[-2] + num**2, num**2, dp2[-1] + num))
    return max(dp2)

print(solve([4, 1, -2, -1]))

Đầu vào

[4, 1, -2, -1]

Đầu ra

17