এই সমস্যায়, আমাদের একটি অ্যারে arr[] এবং Q কোয়েরি দেওয়া আছে। প্রতিটি কোয়েরি দুই টাইপের হতে পারে: ১ম টাইপ - দেওয়া রেঞ্জ [Start - End]-এ সর্বোচ্চ পেয়ার প্রোডাক্ট বের করা। ২য় টাইপ - i-তম ইনডেক্সের এলিমেন্ট আপডেট করা। আমাদের কাজ হল কোয়েরিগুলো সমাধান করার একটি প্রোগ্রাম তৈরি করা।
উদাহরণ দিয়ে বোঝা যাক
ইনপুট: arr = {4, 2, 6, 9, 1}
Q = 3
Q1 = [1, 1, 4]
Q2 = [2, 2, 3]
Q3 = [1, 0, 2]
আউটপুট: 54, 12
ব্যাখ্যা
কোয়েরি ১, টাইপ ১: রেঞ্জ = {2, 6, 9, 1}। সর্বোচ্চ প্রোডাক্ট 6*9 = 54
কোয়েরি ২, টাইপ ২: i = 2, আপডেট করা অ্যারে arr[] = {4, 2, 3, 9, 1}
কোয়েরি ৩, টাইপ ১: রেঞ্জ = {4, 2, 3}। সর্বোচ্চ প্রোডাক্ট 4*3 = 12
সমাধান পদ্ধতি
সমস্যা সমাধানের একটি সহজ পদ্ধতি হল প্রতিটি টাইপ ১ কোয়েরির জন্য পুরো অ্যারে ট্রাভার্স করে সব পেয়ার চেক করা এবং সর্বোচ্চ প্রোডাক্ট বের করা।
C++ প্রোগ্রাম উদাহরণ (সহজ পদ্ধতি)
#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
এই পদ্ধতিটি ভালো কিন্তু সর্বোচ্চ প্রোডাক্ট বের করতে পুরো অ্যারে ট্রাভার্স করতে হয় যা টাইম কমপ্লেক্সিটি বাড়ায়।
দক্ষ সমাধান: সেগমেন্ট টรี ডেটা স্ট্রাকচার
একটি দক্ষ সমাধান হতে পারে সেগমেন্ট টรี ডেটা স্ট্রাকচার ব্যবহার করা সাবঅ্যারের দুটি সর্বোচ্চ উপাদান সংরক্ষণ করার জন্য। এবং তারপর তাদের গুণফল ফেরত দেওয়া।
C++ প্রোগ্রাম উদাহরণ (সেগমেন্ট টรี পদ্ধতি)
#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, int updateVal) {
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
