इस समस्या में, हमें दो सरणियाँ arr1[] आकार n और arr2[] आकार m की दी गई हैं। हमारा कार्य कुछ तत्वों को छोड़कर अधिकतम सबअरे योग खोजने के लिए एक प्रोग्राम बनाना है।
समस्या का विवरण - हमें arr1[] सरणी के उन तत्वों से अधिकतम सबअरे योग खोजने की आवश्यकता है जो arr2[] में मौजूद नहीं हैं।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr1[] = {4, 5, 7, 2, 9}, arr2[] = {1, 9, 2, 7} आउटपुट
9
स्पष्टीकरण
arr1 after removal of elements of arr2[] = {4, 5}
Both can form a subarray, hence sum = 4+5 = 9. समाधान दृष्टिकोण
समस्या का एक सरल समाधान कडाने के एल्गोरिथम का उपयोग कर रहा है जिसमें हम सरणियों के सभी सकारात्मक संक्रामक अनुक्रम पा सकते हैं। इस बाद के तत्वों का योग ज्ञात करें और फिर उनमें से अधिकतम लौटाएं। हम इस तथ्य के आधार पर एल्गोरिदम को अपडेट करेंगे कि हमें अधिकतम सबएरे के लिए एआर 2 [] तत्वों पर विचार करने की आवश्यकता नहीं है और इसके लिए हम खोज एल्गोरिदम का उपयोग करके तत्व खोजेंगे। यदि यह arr2 में मौजूद है, तो हम वर्तमान विंडो को साफ़ कर देंगे और विंडो को रीसेट कर देंगे। जांचें कि क्या योग मैक्ससम से कम है, मैक्ससम =योग।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
#include <iostream>
using namespace std;
int isInArr2(int arr2[], int start, int end, int searchEle){
if (end >= start) {
int mid = start + (end − start) / 2;
if (arr2[mid] == searchEle)
return true;
if (arr2[mid] > searchEle)
return isInArr2(arr2, start, mid − 1, searchEle);
return isInArr2(arr2, mid + 1, end, searchEle);
}
return false;
}
int calcMaxSubArraySum(int arr1[], int arr2[], int n, int m){
int maxSum = −1, sum = 0;
for (int i = 0; i < n; i++) {
if (isInArr2(arr2, 0, m, arr1[i])) {
sum = 0;
continue;
}
sum = max(arr1[i], sum + arr1[i]);
maxSum = max(maxSum, sum);
}
return maxSum;
}
int main(){
int arr1[] = { 5, 4, 7, 2, 9 };
int arr2[] = { 1, 9, 2, 7 };
int n = sizeof(arr1) / sizeof(arr1[0]);
int m = sizeof(arr2) / sizeof(arr2[0]);
cout<<"The maximum Subarray Sum Excluding Certain Elements is
"<<calcMaxSubArraySum(arr1, arr2, n, m);
return 0;
} आउटपुट
The maximum Subarray Sum Excluding Certain Elements is 9
यह समाधान प्रभावी है लेकिन दूसरी सरणी में तत्वों की उपस्थिति की जांच करने के लिए एक बेहतर तरीका हो सकता है जो कुछ गणना समय बचाएगा। मानचित्र का उपयोग करके इसे करने का एक तरीका यहां दिया गया है -
इस दृष्टिकोण में, हम अपने अपडेट किए गए कडाने के एल्गोरिथम का उपयोग करेंगे और एक और अपडेट हमारे खोज एल्गोरिथम को मैप-आधारित चेक के साथ एरे में तत्व की उपस्थिति के लिए प्रतिस्थापित करके किया जाएगा जो प्रभावी होगा।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
#include <bits/stdc++.h>
using namespace std;
int calcMaxSubArraySum(int arr1[], int arr2[], int n, int m){
unordered_map<int,int> checkVal;
for(int i=0;i<m;i++)
checkVal[arr2[i]] = 1;
int maxSum = −1, sum = 0;
for (int i = 0; i < n; i++) {
if (checkVal[arr1[i]]==1) {
sum = 0;
continue;
}
sum = max(arr1[i], sum + arr1[i]);
maxSum = max(maxSum, sum);
}
return maxSum;
}
int main(){
int arr1[] = { 5, 4, 7, 2, 9 };
int arr2[] = { 1, 9, 2, 7 };
int n = sizeof(arr1) / sizeof(arr1[0]);
int m = sizeof(arr2) / sizeof(arr2[0]);
cout<<"The maximum Subarray Sum Excluding Certain Elements is "<<calcMaxSubArraySum(arr1, arr2, n, m);
return 0;
} आउटपुट
The maximum Subarray Sum Excluding Certain Elements is 9