इस समस्या में, हमें एक सरणी गिरफ्तारी [] और क्यू प्रश्न दिए गए हैं। प्रत्येक क्वेरी 2 प्रकारों में से एक हो सकती है, पहली दी गई श्रेणी में अधिकतम जोड़ी उत्पाद खोजने के लिए [प्रारंभ - अंत]। दूसरा मूल्य के साथ ith सूचकांक तत्व को अद्यतन करने के लिए। हमारा काम C++ में अपडेट के साथ रेंज में अधिकतम उत्पाद जोड़ी खोजने के लिए क्वेरीज़ को हल करने के लिए एक प्रोग्राम बनाना है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट: गिरफ्तारी ={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