Chương trình tìm giá trị lớn nhất của phương trình trong Python

Cho mảng points chứa tọa độ (x_i, y_i) đã sắp xếp theo x tăng dần. Cho giá trị k. Tìm max của y_i + y_j + |x_i - x_j| với điều kiện |x_i - x_j| <= k và i < j.

Ví dụ: points = [[2,4],[3,1],[6,11],[7,-9]], k = 1 → kết quả 6 (cặp (2,4) và (3,1): 4+1+|2-3|=6).

Giải thuật (Hai con trỏ)

1. Khởi tạo left = 0, right = 1, max_value = -inf.
2. Trong khi right < len(points):
   • Lấy (xl, yl) = points[left], (xr, yr) = points[right].
   • diff = abs(xr - xl).
   • Nếu left == right: right += 1.
   • Ngược lại nếu diff <= k:
     • m = yl + yr + diff, cập nhật max_value.
     • Nếu yl >= yr - diff: right += 1; ngược lại: left += 1.
   • Ngược lại: left += 1.
3. Trả về max_value.

Ví dụ minh họa

def solve(points, k):
    left, right = 0, 1
    max_value = float('-inf')
    while right < len(points):
        xl, yl = points[left]
        xr, yr = points[right]
        diff = abs(xr - xl)
        if left == right:
            right += 1
        elif diff <= k:
            m = yl + yr + diff
            max_value = max(max_value, m)
            if yl >= yr - diff:
                right += 1
            else:
                left += 1
        else:
            left += 1
    return max_value

points = [[2,4],[3,1],[6,11],[7,-9]]
k = 1
print(solve(points, k))

Đầu vào

[[2,4],[3,1],[6,11],[7,-9]], 1

Đầu ra

6