पायथन में सभी संभावित वैध पथों से अधिकतम अंक खोजने का कार्यक्रम

मान लीजिए कि हमारे पास दो सरणियाँ हैं nums1 और nums2। एक वैध पथ निम्नानुसार परिभाषित किया गया है -

पार करने के लिए nums1 या nums2 चुनें (इंडेक्स-0 से)।
सरणी को बाएँ से दाएँ पार करें।

अब, यदि हम 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 का आकार
sum1 :=0, sum2 :=0
मैं:=0, जे:=0
रेस :=0
जबकि मैं <एम और जे <एन, करते हैं
- अगर nums1[i]
  - sum1 :=sum1 + nums1[i]
  - मैं :=मैं + 1
- अन्यथा जब nums1[i]> nums2[j], तब
  - sum2 :=sum2 + nums2[j]
  - जे:=जे + 1
- अन्यथा,
  - res :=res + अधिकतम योग1, (sum2 + nums1[i])
  - मैं :=मैं + 1
  - जे:=जे + 1
  - योग1 :=0
  - sum2 :=0
जबकि मैं <एम, करता हूं
- sum1 :=sum1 + nums1[i]
- मैं :=मैं + 1
जबकि j
- sum2 :=sum2 + nums2[j]
- जे:=जे + 1
वापसी (res + अधिकतम योग 1, योग 2) मॉड 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]