समस्या कथन
दो क्रमबद्ध सरणियों को देखते हुए ऐसे सरणियों में कुछ सामान्य तत्व हो सकते हैं। किसी भी सरणी की शुरुआत से किसी भी दो सरणी के अंत तक पहुंचने के लिए अधिकतम योग पथ का योग ज्ञात करें। हम एक सरणी से दूसरे सरणी में केवल सामान्य तत्वों पर स्विच कर सकते हैं। ध्यान दें कि सामान्य तत्वों का एक ही अनुक्रमणिका पर होना आवश्यक नहीं है।
अपेक्षित समय जटिलता O(m+n) है जहां m arr1[] में तत्वों की संख्या है और n arrs2 में तत्वों की संख्या है[]
उदाहरण
If given input is then output is 35
arr1[] = {2, 3, 7, 10, 12}
ar2[] = {1, 5, 7, 8}
(1 + 5 + 7 + 10 + 12) = 35 -
1. हम arr2 के पहले तत्व से शुरू करते हैं जो 1 है, फिर हम 5 पर जाते हैं, फिर 7.
-
7 से, हम ar1 (7 सामान्य है) पर स्विच करते हैं और 10 और 12 को पार करते हैं।
एल्गोरिदम
-
मर्ज सॉर्ट की मर्ज प्रक्रिया के समान कुछ करने का विचार है। हमें दोनों सरणियों के लिए सभी सामान्य बिंदुओं के बीच तत्वों के योग की गणना करने की आवश्यकता है। जब भी हम एक उभयनिष्ठ बिंदु देखते हैं, हम दो योगों की तुलना करते हैं और परिणाम में अधिकतम दो जोड़ देते हैं।
-
परिणाम को 0 के रूप में प्रारंभ करें। इसके अलावा दो चर sum1 और sum2 को 0 के रूप में प्रारंभ करें। यहां sum1 और sum2 का उपयोग तत्व के योग को क्रमशः arr1[] और arr2[] में संग्रहीत करने के लिए किया जाता है। ये योग दो सामान्य बिंदुओं के बीच हैं
-
अब दोनों सरणियों के तत्वों को पार करने के लिए एक लूप चलाएँ। ट्रैवर्सिंग के दौरान arr1[] और arr2[]
. के मौजूदा तत्वों की तुलना करें-
यदि arr1[] का वर्तमान तत्व arr2[] के वर्तमान तत्व से छोटा है, तो sum1 को अपडेट करें, अन्यथा यदि arr2[] का वर्तमान तत्व छोटा है, तो योग को अपडेट करें
-
यदि 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 << "Maximum sum path = " << maxPathSum(arr1, arr2, m, n) << endl;
return 0;
} आउटपुट
जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है -
Maximum sum path = 35