এই সমস্যায়, আমাদেরকে n আকারের arr1[] এবং m আকারের arr2[] দুটি অ্যারে দেওয়া হয়েছে। আমাদের কাজ হল নির্দিষ্ট কিছু উপাদান বাদ দিয়ে সর্বাধিক সাবয়ারের যোগফল খুঁজে বের করার জন্য একটি প্রোগ্রাম তৈরি করা।
সমস্যা বর্ণনা − আমাদের অ্যারের অ্যারে 1[] উপাদানগুলি থেকে সর্বাধিক সাবয়ারের যোগফল খুঁজে বের করতে হবে যা 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 তে উপস্থিত থাকে, আমরা বর্তমান উইন্ডোটি পরিষ্কার করব এবং উইন্ডোটি পুনরায় সেট করব। যোগফল 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
এই সমাধানটি কার্যকর কিন্তু দ্বিতীয় অ্যারের উপাদানগুলির উপস্থিতি পরীক্ষা করার জন্য একটি ভাল পদ্ধতি হতে পারে যা কিছু গণনার সময় বাঁচাবে। এখানে একটি মানচিত্র -
ব্যবহার করে এটি করার একটি উপায় রয়েছেএই পদ্ধতিতে, আমরা আমাদের আপডেট করা Kadane-এর অ্যালগরিদম ব্যবহার করব এবং আরও একটি আপডেট করা হবে আমাদের সার্চিং অ্যালগরিদমকে একটি ম্যাপ-ভিত্তিক চেক দিয়ে প্রতিস্থাপন করে অ্যারেতে উপাদানটির উপস্থিতির জন্য যা কার্যকর হবে৷
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
#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
