โปรแกรมหาคู่ระยะไกลสุดจากสองลิสต์ตัวเลขใน Python

สมมติว่ามีรายการตัวเลข A และ B ความยาวเท่ากัน ต้องการหาค่าสูงสุดของ |a[i]-a[j]| + |b[i]-b[j]| + |i-j| สำหรับทุก 0 ≤ i < j < n

ตัวอย่าง: A = [2,4,10,6], B = [3,4,7,5] ผลลัพธ์ 14 ที่ i=0, j=2: |2-10|+|3-7|+|0-2| = 8+4+2=14

ขั้นตอนการแก้ปัญหา

1. ans = 0, n = len(a)
2. วน 4 กรณีเครื่องหมาย (s,t) in [(-1,-1),(-1,1),(1,-1),(1,1)]:
   • cur_min = inf, cur_max = -inf
   • วน i จาก 0 ถึง n-1:
     • 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)
3. คืน ans

ตัวอย่างโค้ด

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))

อินพุต

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

เอาต์พุต

14