C++ में दो सरणियों में अधिकतम योग पथ (Maximum Sum Path in Two Arrays)

समस्या कथन

दो क्रमबद्ध सरणियां दी गई हैं जिनमें कुछ सामान्य तत्व हो सकते हैं। किसी भी सरणी की शुरुआत से किसी भी सरणी के अंत तक पहुंचने के लिए अधिकतम योग पथ का योग ढूंढें। हम केवल सामान्य तत्वों पर एक सरणी से दूसरी सरणी पर जा सकते हैं। ध्यान दें कि सामान्य तत्वों का समान इंडेक्स पर होना आवश्यक नहीं है।

अपेक्षित समय जटिलता O(m+n) है जहां m, arr1[] में तत्वों की संख्या है और n, arr2[] में तत्वों की संख्या है।

उदाहरण

यदि दिया गया इनपुट है तो आउटपुट 35 है
arr1[] = {2, 3, 7, 10, 12}
arr2[] = {1, 5, 7, 8}
(1 + 5 + 7 + 10 + 12) = 35

• हम arr2 के पहले तत्व 1 से शुरू करते हैं, फिर 5 पर जाते हैं, फिर 7 पर।
• 7 से, हम arr1 पर स्विच करते हैं (7 सामान्य है) और 10 और 12 को पार करते हैं।

एल्गोरिदम

• विचार मर्ज सॉर्ट की मर्ज प्रक्रिया के समान कुछ करना है। हमें दोनों सरणियों के लिए सभी सामान्य बिंदुओं के बीच के तत्वों के योग की गणना करने की आवश्यकता है। जब भी हम एक सामान्य बिंदु देखते हैं, हम दोनों योगों की तुलना करते हैं और उनमें से अधिकतम को परिणाम में जोड़ते हैं।
• परिणाम को 0 से आरंभ करें। दो वेरिएबल sum1 और sum2 को 0 से आरंभ करें। यहां sum1 और sum2 का उपयोग arr1[] और arr2[] में तत्वों के योग को संग्रहीत करने के लिए किया जाता है। ये योग दो सामान्य बिंदुओं के बीच के होते हैं।
• अब दोनों सरणियों के तत्वों को पार करने के लिए एक लूप चलाएं। पार करते समय arr1[] और arr2[] के वर्तमान तत्वों की तुलना करें:
  • यदि arr1[] का वर्तमान तत्व arr2[] के वर्तमान तत्व से छोटा है, तो sum1 अपडेट करें, अन्यथा यदि arr2[] का वर्तमान तत्व छोटा है, तो sum2 अपडेट करें
  • यदि arr1[] और arr2[] के वर्तमान तत्व समान हैं, तो sum1 और sum2 का अधिकतम लें और इसे परिणाम में जोड़ें। सामान्य तत्व को भी परिणाम में जोड़ें

उदाहरण

#include <bits/stdc++.h>
using namespace std;

int max(int x, int y){
    return (x > y) ? x : y;
}

int maxPathSum(int *arr1, int *arr2, int m, int n){
    int i = 0, j = 0;
    int result = 0, sum1 = 0, sum2 = 0;
    while (i < m && j < n) {
        if (arr1[i] < arr2[j]) {
            sum1 += arr1[i++];
        } else if (arr1[i] > arr2[j]) {
            sum2 += arr2[j++];
        } else {
            result += max(sum1, sum2);
            sum1 = 0, sum2 = 0;
            while (i < m && j < n && arr1[i] == arr2[j]) {
                result = result + arr1[i++];
                j++;
            }
        }
    }
    while (i < m) {
        sum1 += arr1[i++];
    }
    while (j < n) {
        sum2 += arr2[j++];
    }
    result += max(sum1, sum2);
    return result;
}

int main(){
    int arr1[] = {2, 3, 7, 10, 12};
    int arr2[] = {1, 5, 7, 8};
    int m = sizeof(arr1)/sizeof(arr1[0]);
    int n = sizeof(arr2)/sizeof(arr2[0]);
    cout << "अधिकतम योग पथ = " << maxPathSum(arr1, arr2, m, n) << endl;
    return 0;
}

आउटपुट

अधिकतम योग पथ = 35