इस समस्या में, हमें आकार n की एक सरणी arr1[] और आकार m की एक सरणी arr2[] दी गई है। हमारा कार्य एक प्रोग्राम बनाना है जो कुछ तत्वों को छोड़कर अधिकतम उपसरणी योग ढूंढे।
समस्या विवरण
हमें सरणी arr1[] के तत्वों से अधिकतम उपसरणी योग ढूंढना है जो arr2[] में मौजूद नहीं हैं।
उदाहरण
इनपुट
arr1[] = {4, 5, 7, 2, 9}, arr2[] = {1, 9, 2, 7}
आउटपुट
9
व्याख्या
arr2[] के तत्वों को हटाने के बाद arr1 = {4, 5}
दोनों एक उपसरणी बना सकते हैं, इसलिए योग = 4+5 = 9।
समाधान दृष्टिकोण
समस्या का एक सरल समाधान कडाने के एल्गोरिदम (Kadane's Algorithm) का उपयोग करना है जिसमें हम सरणी के सभी धनात्मक सन्निकट अनुक्रम ढूंढ सकते हैं। इस उपअनुक्रम के सभी तत्वों का योग ढूंढें और फिर उनमें से अधिकतम वापस करें। हम एल्गोरिदम को इस तथ्य के आधार पर अपडेट करेंगे कि हमें arr2[] के तत्वों पर अधिकतम उपसरणी के लिए विचार नहीं करना है और इसके लिए हम खोज एल्गोरिदम का उपयोग करके तत्व को खोजेंगे। यदि यह arr2 में मौजूद है, तो हम वर्तमान विंडो को साफ कर देंगे और विंडो को रीसेट कर देंगे। जांचें कि क्या योग maxSum से कम है, maxSum = योग।
उदाहरण
हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम,
#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 checkVal;
for(int i=0;i
आउटपुट
The maximum Subarray Sum Excluding Certain Elements is 9
