এই সমস্যায়, আমাদেরকে একটি অ্যারে arr[] এবং Q প্রশ্ন দেওয়া হয়েছে। প্রতিটি ক্যোয়ারী 2 প্রকারের একটি হতে পারে, একটি নির্দিষ্ট পরিসরে সর্বাধিক জোড়া পণ্যটি খুঁজে পেতে 1ম [শুরু - শেষ]। 2য় মান সহ ith সূচক উপাদান আপডেট করতে. আমাদের কাজ হল C++-এ আপডেট সহ সর্বাধিক পণ্যের জুড়ি খুঁজে পেতে প্রশ্নের সমাধান করার জন্য একটি প্রোগ্রাম তৈরি করা।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট: arr ={4, 2, 6, 9, 1}
প্রশ্ন =3
Q1 =[1, 1, 4]
Q2 =[2, 2, 3]
Q3 =[1, 0, 2]
আউটপুট: 54, 12
ব্যাখ্যা
ক্যোয়ারী 1 এর জন্য, 1 টাইপ করুন:রেঞ্জ ={2, 6, 9, 1}। সর্বাধিক পণ্য 6*9 =54
ক্যোয়ারী 2 এর জন্য, টাইপ করুন 2:i =2 , আপডেট করা অ্যারে arr[] ={4, 2, 3, 9, 1}
ক্যোয়ারী 3 এর জন্য, 1 টাইপ করুন:রেঞ্জ ={4, 2, 3}। সর্বাধিক পণ্য 4*3 =12
সমাধান পদ্ধতি
সমস্যা সমাধানের জন্য, আমরা একটি সহজ পদ্ধতি আছে. যেটি টাইপ ওয়ানের প্রতিটি প্রশ্নের জন্য পুরো অ্যারে অতিক্রম করে এবং প্রতিটি জোড়ার পণ্য পরীক্ষা করে তারপর তাদের মধ্যে সর্বাধিক পণ্য জোড়া খুঁজে বের করে।
উদাহরণ
#include <iostream>
using namespace std;
int max(int a, int b){
if(a>b)
return a;
return b;
}
int findMaxProductPair(int arr[], int n, int start, int end){
int maxProd = 0;
for(int i = start; i <= end; i++){
for(int j = i+1; j <= end; j++){
maxProd = max(maxProd, (arr[i]*arr[j]));
}
}
return maxProd;
}
int main(){
int arr[] = {4, 2, 6, 9, 1, 5};
int n = 6;
int Q = 3;
int query[Q][3] = {{1, 1, 4}, {2, 2, 3}, {1, 0, 2}};
for(int i = 0; i < Q; i++){
if(query[i][0] == 1){
cout<<"The maximum product pair in the range is "<<findMaxProductPair(arr, n, query[i][1], query[i][2])<<"\n";
}
else if(query[i][0] == 2){
cout<<"Updating values...\n";
arr[query[i][1]] = query[i][2];
}
}
return 0;
} আউটপুট
The maximum product pair in the range is 54 Updating values... The maximum product pair in the range is 12
এই পদ্ধতিটি ভাল তবে সর্বাধিক পণ্যটি খুঁজে পেতে, আমাদের পুরো অ্যারেটি অতিক্রম করতে হবে যা সময়ের জটিলতা বাড়ায়৷
একটি দক্ষ সমাধান সাব-অ্যারের দুটি বৃহত্তম উপাদান সংরক্ষণ করতে একটি সেগমেন্ট ট্রি ডেটা কাঠামো ব্যবহার করা যেতে পারে। এবং তারপর তাদের পণ্য ফেরত দিন।
উদাহরণ
#include <iostream>
using namespace std;
struct segment {
int maxEle;
int secMax;
};
segment findMaxProductPair(segment* prodTree, int index, int start, int end, int L, int R) {
segment result;
result.maxEle = -1;
result.secMax = -1;
if (L > end || R < start || start > end)
return result;
if (start >= L && end <= R)
return prodTree[index];
int middleIndex = (start + end) / 2;
segment left = findMaxProductPair(prodTree, 2 * index, start,middleIndex, L, R);
segment right = findMaxProductPair(prodTree, 2 * index + 1,middleIndex + 1, end, L, R);
result.maxEle = max(left.maxEle, right.maxEle);
result.secMax = min(max(left.maxEle, right.secMax),max(right.maxEle, left.secMax));
return result;
}
void update(segment* prodTree, int index, int start, int end, int i, intupdateVal) {
if (i < start || i > end)
return;
if (start == end) {
prodTree[index].maxEle = updateVal;
prodTree[index].secMax = -1;
return;
}
int middleIndex = (start + end) / 2;
update(prodTree, 2 * index, start, middleIndex, i, updateVal);
update(prodTree, 2 * index + 1, middleIndex + 1, end, i, updateVal);
prodTree[index].maxEle = max(prodTree[2 * index].maxEle,prodTree[2 * index + 1].maxEle);
prodTree[index].secMax = min(max(prodTree[2 * index].maxEle,prodTree[2 * index + 1].secMax), max(prodTree[2 * index + 1].maxEle,prodTree[2 * index].secMax));
}
void buildtree(segment* prodTree, int* arr, int index, int start, int end) {
if (start > end) {
return;
}
if (start == end) {
prodTree[index].maxEle = arr[start];
prodTree[index].secMax = -1;
return;
}
int middleIndex = (start + end) / 2;
buildtree(prodTree, arr, 2 * index, start, middleIndex);
buildtree(prodTree, arr, 2 * index + 1, middleIndex + 1, end);
int maximum = max(prodTree[2 * index].maxEle, prodTree[2 * index + 1].maxEle);
int secMaximum = min(max(prodTree[2 * index].maxEle, prodTree[2 * index + 1].secMax),max(prodTree[2 * index + 1].maxEle, prodTree[2 * index].secMax));
prodTree[index].maxEle = maximum;
prodTree[index].secMax = secMaximum;
}
int main() {
int arr[] = {4, 2, 6, 9, 1, 5};
int n = 6;
int Q = 3;
segment* prodTree = new segment[4 * n + 1];
buildtree(prodTree, arr, 1, 0, n - 1);
int query[Q][3] = {{1, 1, 4}, {2, 2, 3}, {1, 0, 2}};
for(int i = 0; i < Q; i++){
if(query[i][0] == 1){
segment result = findMaxProductPair(prodTree, 1, 0, n - 1,query[i][1] , query[i][2]);
cout<<"The maximum product pair in the range is "<<(result.maxEle*result.secMax)<<"\n";
}
else if(query[i][0] == 2){
cout<<"Updating values...\n";
update(prodTree, 1, 0, n - 1, query[i][1], query[i][2]);
}
}
return 0;
} আউটপুট
The maximum product pair in the range is 54 Updating values... The maximum product pair in the range is 12
