在C++中用最大值更新查找最大乘积对的查询

Z时代
2024-01-10
分类：综合

在这个问题中，我们得到了一个数组arr []和Q查询。每个查询可以是2种类型之一，第1种用于查找给定范围内的最大对乘积[Start-End]。第2次使用值更新第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：range = {2，6，9，1}。最大乘积6 * 9 = 54

对于查询2，键入2：i = 2，更新数组arr [] = {4，2，3，9，1}

对于查询3，键入1：range = {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;
}