Trong bài toán này, chúng ta được cung cấp một dãy arr [] và truy vấn Q. Mỗi Truy vấn có thể là một trong 2 loại, thứ nhất để tìm sản phẩm cặp tối đa trong một phạm vi nhất định [Bắt đầu - Kết thúc]. Thứ 2 để cập nhật phần tử chỉ mục thứ i với giá trị. Nhiệm vụ của chúng tôi là tạo một chương trình giải quyết các Truy vấn để tìm ra cặp sản phẩm tối đa trong các bản cập nhật rangewith trong C ++.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào: arr ={4, 2, 6, 9, 1}
Q =3
Q1 =[1, 1, 4]
Quý 2 =[2, 2, 3]
Q3 =[1, 0, 2]
Đầu ra: 54, 12
Giải thích
Đối với truy vấn 1, hãy nhập 1:range ={2, 6, 9, 1}. Sản phẩm tối đa 6 * 9 =54
Đối với truy vấn 2, hãy nhập 2:i =2, mảng được cập nhật arr [] ={4, 2, 3, 9, 1}
Đối với truy vấn 3, nhập 1:range ={4, 2, 3}. Sản phẩm tối đa 4 * 3 =12
Phương pháp tiếp cận giải pháp
Để giải quyết vấn đề, chúng tôi có một cách tiếp cận đơn giản. Điều này dành cho mọi truy vấn của loại một đi qua toàn bộ mảng và kiểm tra sản phẩm của từng cặp và sau đó tìm ra cặp sản phẩm tối đa trong số chúng.
Ví dụ
#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;
} Đầu ra
The maximum product pair in the range is 54 Updating values... The maximum product pair in the range is 12
Cách tiếp cận này là tốt nhưng để tìm ra sản phẩm tối đa, chúng ta cần đi qua mảng lỗ hổng làm tăng độ phức tạp về thời gian.
Một giải pháp hiệu quả có thể sử dụng cấu trúc dữ liệu cây phân đoạn để lưu trữ hai phần tử lớn nhất của mảng con. Và sau đó trả lại sản phẩm của họ.
Ví dụ
#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;
} Đầu ra
The maximum product pair in the range is 54 Updating values... The maximum product pair in the range is 12