두 개의 배열 nums1과 nums2가 있다고 가정합니다. 유효한 경로는 다음과 같이 정의됩니다 -
-
(index-0에서) 순회할 nums1 또는 nums2를 선택합니다.
-
왼쪽에서 오른쪽으로 배열을 탐색합니다.
이제 nums1 및 nums2에 있는 값을 통해 이동하는 경우 다른 배열의 경로를 변경할 수 있습니다. 여기서 점수는 유효한 경로에 있는 고유한 값의 합계입니다. 가능한 모든 유효한 경로에서 얻을 수 있는 최대 점수를 찾아야 합니다. 답이 너무 크면 10^9+7 모듈로 결과를 반환합니다.
따라서 입력이 nums1 =[3,5,6,9,11] nums2 =[5,7,9,10]과 같으면 출력은 -
이기 때문에 35가 됩니다.-
nums1부터 유효한 경로는 [3,5,6,9,11], [3,5,6,9,10], [3,5,7,9,10], [3,5,7, 9,11]
-
nums2부터 유효한 경로는 [5,7,9,10], [5,6,9,11], [5,6,9,10], [5,7,9,11]
입니다.
따라서 최대값은 [3,5,7,9,11]입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
M :=nums1의 크기, N :=nums2의 크기
-
합계1 :=0, 합계2 :=0
-
i :=0, j :=0
-
해상도 :=0
-
동안 i
-
nums1[i]
-
합계1 :=합계1 + 숫자1[i]
-
나는 :=나는 + 1
-
-
그렇지 않으면 nums1[i]> nums2[j]일 때
-
sum2 :=sum2 + nums2[j]
-
j :=j + 1
-
-
그렇지 않으면
-
res :=res + sum1의 최대값, (sum2 + nums1[i])
-
나는 :=나는 + 1
-
j :=j + 1
-
합계1 :=0
-
합계2 :=0
-
-
-
내가
-
합계1 :=합계1 + 숫자1[i]
-
나는 :=나는 + 1
-
-
j
동안 -
sum2 :=sum2 + nums2[j]
-
j :=j + 1
-
-
return(res + sum1의 최대값, sum2) mod 10^9+7
예
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
def solve(nums1, nums2):
M, N = len(nums1), len(nums2)
sum1, sum2 = 0, 0
i, j = 0, 0
res = 0
while i < M and j < N:
if nums1[i] < nums2[j]:
sum1 += nums1[i]
i += 1
elif nums1[i] > nums2[j]:
sum2 += nums2[j]
j += 1
else:
res += max(sum1, sum2) + nums1[i]
i += 1
j += 1
sum1 = 0
sum2 = 0
while i < M:
sum1 += nums1[i]
i += 1
while j < N:
sum2 += nums2[j]
j += 1
return (res + max(sum1, sum2)) % 1000000007
nums1 = [3,5,6,9,11]
nums2 = [5,7,9,10]
print(solve(nums1, nums2)) 입력
[3,5,6,9,11], [5,7,9,10]
출력
35