মনে করুন nums1 এবং nums2 নামক দুটি অ্যারে আছে। একটি বৈধ পথ নিচেরভাবে ডিফাইন করা হয়েছে:
nums1 অথবা nums2 সিলেক্ট করুন ট্রাভার্স করার জন্য (ইনডেক্স-০ থেকে)।
অ্যারেটি বাম থেকে ডানে ট্রাভার্স করুন।
এখন, যদি আমরা যেকোনো ভ্যালুতে পৌঁছাই যা nums1 এবং nums2 দুটোতেই থাকে, তবে আমরা অন্য অ্যারেতে সুইচ করতে পারি। এখানে স্কোর হলো একটি বৈধ পথে যুনিক ভ্যালুগুলোর যোগফল। সব সম্ভাব্য বৈধ পথ থেকে সর্বোচ্চ স্কোর বের করতে হবে। উত্তর বড় হলে 10^9+7 দিয়ে মডুলো রিটার্ন করুন।
যেমন, ইনপুট nums1 = [3,5,6,9,11], nums2 = [5,7,9,10] হলে, আউটপুট হবে ৩৫ কারণ:
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
যখন i < M এবং j < N, तब
যদি nums1[i] < nums2[j] হয়, তবে
sum1 += nums1[i], i++
অন্যথায় যদি nums1[i] > nums2[j] হয়, তবে
sum2 += nums2[j], j++
অন্যথায় (সমান হলে),
res += max(sum1, sum2) + nums1[i]
i++, j++
sum1 := 0, sum2 := 0
যখন i < M, तब
sum1 += nums1[i], i++
যখন j < N, तब
sum2 += nums2[j], j++
return (res + max(sum1, sum2)) % 1000000007
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বোঝার জন্য:
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] > nums[2][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
