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

मान लीजिए हमारे पास दो सरणियाँ 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
i := 0, j := 0
res := 0
जब तक 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 + sum1 और (sum2 + nums1[i]) का अधिकतम
  - i := i + 1
  - j := j + 1
  - sum1 := 0
  - sum2 := 0
जब तक i < M, करें
- sum1 := sum1 + nums1[i]
- i := i + 1
जब तक j < N, करें
- sum2 := sum2 + nums2[j]
- j := 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]