Python의 두 숫자 목록에서 가장 큰 거리 쌍을 찾는 프로그램

<시간/>

A와 B라는 두 개의 숫자 목록이 있고 길이가 같다고 가정합니다. 모든 0 ≤ i

따라서 입력이 A =[2, 4, 10, 6] B =[3, 4, 7, 5]인 경우 출력은 i =0 및 j =2일 때와 같이 14가 되고 | 2 - 10| + |3 - 7| + |1 - 3|.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

ans :=0
n :=크기
[(-1, -1) ,(-1, 1) ,(1, -1) ,(1, 1) ]의 각 쌍(s, t)에 대해, do
- cur_min :=무한대
- cur_max :=-무한대
- 0에서 n 사이의 i에 대해
  - tmp :=s * a[i] + t * b[i] + i
  - cur_min :=cur_min의 최소값, tmp
  - cur_max :=cur_max, tmp의 최대값
- ans :=ans의 최대값, (cur_max - cur_min)
반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

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]