แบบสอบถามเพื่อค้นหาคู่ผลิตภัณฑ์สูงสุดในช่วงที่มีการอัพเดตใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] และคิวรี Q แบบสอบถามแต่ละรายการสามารถเป็นหนึ่งใน 2 ประเภท อันดับแรกเพื่อค้นหาผลิตภัณฑ์คู่สูงสุดในช่วงที่กำหนด [เริ่ม - สิ้นสุด ] ครั้งที่ 2 เพื่ออัปเดตองค์ประกอบดัชนี ith ด้วยค่า งานของเราคือการสร้างโปรแกรมเพื่อแก้ปัญหาการสืบค้นเพื่อค้นหาคู่ผลิตภัณฑ์สูงสุดในช่วงที่มีการอัพเดทใน C++

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล: arr ={4, 2, 6, 9, 1}

Q =3

ไตรมาสที่ 1 =[1, 1, 4]

ไตรมาสที่ 2 =[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;
}

ผลลัพธ์

The maximum product pair in the range is 54
Updating values...
The maximum product pair in the range is 12