nums1과 nums2라는 두 개의 배열이 있고 동일한 수의 요소 N이 있다고 가정합니다. 이제 1에서 N까지의 N 요소가 있는 집합 S를 고려합니다. (nums1[i1] + nums1[i2] + 의 값을 찾아야 합니다. .. nums1[ik])^2 + (nums2[i1] + nums2[i2] + ... nums2[ik])^2 여기서 {i1, i2, ... ik}는 집합 S의 비어 있지 않은 부분 집합입니다. .
따라서 입력이 nums1 =[-1, 6] nums2 =[5, 4]와 같으면 출력은 106이 됩니다.
- (-1)^2 + (5)^2 =26
- (6)^2 + (4)^2 =50
- (-1 + 6)^2 + (5 + 4)^2 =106
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- vs :=범위 0에서 nums1 - 1 사이의 각 i에 대한 쌍(nums1[i], nums2[i]) 목록
- vs :=vs의 각 v에 대해 v[1]/v[0]의 tan-inverse로 vs를 정렬합니다.
- 최고:=0
- 0에서 vs - 1의 크기 범위에 있는 i에 대해
- u :=대[i]
- l :=u[0]*u[0]+u[1]*u[1]
- vs의 연결 목록에 있는 각 v에 대해 인덱스 i+1에서 (i+ size of vs - 1)까지 vs 다시, do
- t1 :=(u[0]+v[0], u[1]+v[1])
- t2 :=t1[0]*t1[0]+t1[1]*t1[1]
- t2>=l이면
- u :=t1
- l :=t2
- 만약 내가> 최고라면
- 최고:=l
- u :=대[i]
- l :=u[0]*u[0]+u[1]*u[1]
- 인덱스 i+1에서 vs -1의 i+ 크기까지 vs 및 vs를 역으로 연결한 목록의 각 v에 대해, do
- t1 :=(u[0]+v[0], u[1]+v[1])
- t2 :=t1[0]*t1[0]+t1[1]*t1[1]
- t2>=l이면
- u :=t1
- l :=t2
- 만약 내가> 최고라면
- 최고의 수익
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
from math import atan2 def solve(nums1, nums2): vs = zip(nums1,nums2) vs = sorted(vs, key=lambda v: atan2(v[1],v[0])) best = 0 for i in range(len(vs)): u = vs[i] l = u[0]*u[0]+u[1]*u[1] for v in (vs+vs)[i+1:(i+len(vs))]: t1 = (u[0]+v[0],u[1]+v[1]) t2 = t1[0]*t1[0]+t1[1]*t1[1] if t2 >= l: u = t1 l = t2 if l > best: best = l u = vs[i] l = u[0]*u[0]+u[1]*u[1] for v in reversed((vs+vs)[i+1:(i+len(vs))]): t1 = (u[0]+v[0],u[1]+v[1]) t2 = t1[0]*t1[0]+t1[1]*t1[1] if t2 >= l: u = t1 l = t2 if l > best: best = l return best nums1 = [-1, 6] nums2 = [5, -4] print(solve(nums1, nums2))
입력
[-1, 6], [5, -4]
출력
52