2D 평면의 좌표점을 포함하는 점이라는 배열이 있다고 가정하고 x값으로 정렬됩니다. 여기서 점[i] =(x_i, y_i)이므로 x_i
따라서 입력이 포인트 =[[2,4],[3,1],[6,11],[7,-9]] k =1과 같으면 처음 두 포인트가 있기 때문에 출력은 6이 됩니다. 조건을 만족 |xi - xj| <=1 이제 방정식을 계산하면 4+ 1 + |2 - 3| =6. 세 번째 및 네 번째 점도 조건을 충족하고 11 + -9 + |6 - 7| 값을 반환합니다. =3이므로 최대값은 6입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
왼쪽 :=0, 오른쪽 :=1
-
max_value :=-inf
-
오른쪽 <포인트 크기, 수행
동안-
(xl, yl) :=포인트[왼쪽]
-
(xr, yr) :=포인트[오른쪽]
-
차이 :=|xr - xl|
-
왼쪽이 오른쪽과 같으면
-
오른쪽 :=오른쪽 + 1
-
-
그렇지 않으면 diff <=k일 때
-
m :=yl + yr + diff
-
max_value :=max_value 및 m의 최대값
-
yl>=yr - diff이면
-
오른쪽 :=오른쪽 + 1
-
-
그렇지 않으면
-
왼쪽 :=왼쪽 + 1
-
-
그렇지 않으면
-
왼쪽 :=왼쪽 + 1
-
-
-
-
최대값 반환
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
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))
입력
[[2,4],[3,1],[6,11],[7,-9]], 1
출력
6