파이썬에서 방정식의 최대값을 찾는 프로그램

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