이 문제에서는 배열 arr[] 및 Q 쿼리가 제공됩니다. 각 Query는 2가지 유형 중 하나일 수 있습니다. 첫 번째는 주어진 범위 [Start - End ]에서 최대 쌍 제품을 찾는 것입니다. 두 번째는 i번째 인덱스 요소를 값으로 업데이트합니다. 우리의 임무는 C++에서 업데이트된 범위에서 최대 제품 쌍을 찾기 위해 쿼리를 해결하는 프로그램을 만드는 것입니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력: arr ={4, 2, 6, 9, 1}
Q =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
솔루션 접근 방식
문제를 해결하기 위해 간단한 접근 방식이 있습니다. 이는 유형 1의 모든 쿼리에 대해 전체 배열을 탐색하고 모든 쌍의 제품을 확인한 다음 그 중에서 최대 제품 쌍을 찾는 것입니다.
예시
#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