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