สมมติว่าเรามีสองอาร์เรย์ nums1 และ nums2 เส้นทางที่ถูกต้องถูกกำหนดดังนี้ -
-
เลือก nums1 หรือ nums2 ที่จะข้าม (จาก index-0)
-
สำรวจอาร์เรย์จากซ้ายไปขวา
ตอนนี้ หากเรากำลังเคลื่อนผ่านค่าใดๆ ที่มีอยู่ใน nums1 และ nums2 เราสามารถเปลี่ยนเส้นทางไปยังอาร์เรย์อื่นได้ คะแนนคือผลรวมของค่าที่ไม่ซ้ำในเส้นทางที่ถูกต้อง เราต้องหาคะแนนสูงสุดที่เราจะได้รับจากเส้นทางที่เป็นไปได้ทั้งหมด หากคำตอบมีขนาดใหญ่เกินไป ให้ส่งคืนผลลัพธ์ modulo 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
-
sum1 :=0, sum2 :=0
-
ผม :=0, j :=0
-
res :=0
-
ในขณะที่ i
-
ถ้า nums1[i]
-
sum1 :=sum1 + nums1[i]
-
ผม :=ผม + 1
-
-
มิฉะนั้นเมื่อ nums1[i]> nums2[j] แล้ว
-
sum2 :=sum2 + nums2[j]
-
เจ :=เจ + 1
-
-
มิฉะนั้น
-
res :=res + สูงสุดของ sum1, (sum2 + nums1[i])
-
ผม :=ผม + 1
-
เจ :=เจ + 1
-
sum1 :=0
-
sum2 :=0
-
-
-
ในขณะที่ฉัน
-
sum1 :=sum1 + nums1[i]
-
ผม :=ผม + 1
-
-
ในขณะที่ j
-
sum2 :=sum2 + nums2[j]
-
เจ :=เจ + 1
-
-
ผลตอบแทน (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
