Chương trình tìm giá trị tối đa biểu thức mảng với chỉ số i ≤ j trong Python

Cho hai mảng nums (tăng chặt) và values cùng độ dài. Tìm giá trị lớn nhất của v = values[i] + values[j] + nums[j] - nums[i] với i ≤ j.

Ví dụ: nums = [1, 2, 7], values = [-4, 6, 5] → kết quả 16 (tại i=1, j=2: 6+5+7-2=16).

Thuật toán giải quyết (O(n))

Biểu thức viết lại: (values[i] - nums[i]) + (values[j] + nums[j]). Với i ≤ j, ta duy trì:

• ans1 = max(values[i] - nums[i]) cho i đã duyệt
• ans2 = max(values[j] + nums[j]) cho j hiện tại

Kết quả = ans1 + ans2 (vì i ≤ j đảm bảo bằng cách cập nhật ans1 trước ans2 tại mỗi bước).

Ví dụ minh họa

from math import inf

def solve(nums, values):
    ans1 = -inf
    ans2 = -inf
    for i in range(len(nums)):
        ans1 = max(ans1, values[i] - nums[i])
        ans2 = max(ans2, values[i] + nums[i])
    return ans1 + ans2

nums = [1, 2, 7]
values = [-4, 6, 5]
print(solve(nums, values))

Đầu vào

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

Đầu ra

16