Chương trình tìm cặp khoảng cách lớn nhất từ hai danh sách số trong Python

Mô tả bài toán

Cho hai danh sách A và B cùng độ dài n. Tìm giá trị lớn nhất của |a[i]-a[j]| + |b[i]-b[j]| + |i-j| với mọi 0 ≤ i < j < n.

Ví dụ: A = [2,4,10,6], B = [3,4,7,5] → đầu ra 14 (tại i=0, j=2).

Giải thuật (Biến đổi Manhattan)

1. Khởi tạo ans = 0.
2. Duyệt 4 cặp dấu (s,t) trong {(-1,-1), (-1,1), (1,-1), (1,1)}:
   • Tính tmp = s*a[i] + t*b[i] + i cho mọi i.
   • Tìm cur_min và cur_max của tmp.
   • ans = max(ans, cur_max - cur_min).
3. Trả về ans.

Ví dụ mã Python

class Solution:
    def solve(self, a, b):
        ans = 0
        n = len(a)
        for s, t in [(-1, -1), (-1, 1), (1, -1), (1, 1)]:
            cur_min = float("inf")
            cur_max = float("-inf")
            for i in range(n):
                tmp = s * a[i] + t * b[i] + i
                cur_min = min(cur_min, tmp)
                cur_max = max(cur_max, tmp)
            ans = max(ans, cur_max - cur_min)
        return ans

ob = Solution()
A = [2, 4, 10, 6]
B = [3, 4, 7, 5]
print(ob.solve(A, B))

Đầu vào

[2, 4, 10, 6],[3, 4, 7, 5]

Đầu ra

14