ชุดย่อยผลิตภัณฑ์สูงสุดและต่ำสุดใน C++

เราได้รับอาร์เรย์ของจำนวนเต็มขนาด N เป้าหมายที่นี่คือการหาชุดย่อยของผลิตภัณฑ์สูงสุดและต่ำสุด เราจะทำเช่นนี้โดยใช้ตัวแปรผลิตภัณฑ์ 2 รายการ ตัวแปรหนึ่งสำหรับผลิตภัณฑ์ขั้นต่ำที่ minProd ตรวจพบ และอีกรายการสำหรับผลิตภัณฑ์สูงสุดที่ตรวจพบคือ maxProd

ขณะสำรวจอาร์เรย์ เราจะคูณแต่ละองค์ประกอบด้วย minProd และ maxProd ตรวจสอบผลิตภัณฑ์สูงสุดก่อนหน้า ผลิตภัณฑ์ขั้นต่ำก่อนหน้า ผลิตภัณฑ์สูงสุดปัจจุบัน ผลิตภัณฑ์ขั้นต่ำปัจจุบัน และองค์ประกอบปัจจุบันด้วย

อินพุต

Arr[]= { 1,2,5,0,2 }

ผลลัพธ์

Maximum Product: 20
Minimum Product: 0

คำอธิบาย เริ่มจากองค์ประกอบที่สองในอาร์เรย์ด้วยค่า maxProd และ minProd ที่เริ่มต้นด้วย 1 ( องค์ประกอบแรก )

Arr[1]: 1*2=2, 1*2=2, maxProd=2, minProd=1
Arr[2]: 2*5=10, 1*5=5, maxProd=10, minProd=1
Arr[3]: 10*0=0, 1*0=0, maxProd=10, minProd=0
Arr[4]: 10*2=20, 0*2=0, maxProd=20, minProd=0

อินพุต

Arr[]= { -1,2,-5,0,2 }

ผลลัพธ์

Maximum Product: 20
Minimum Product: -20

คำอธิบาย − สำหรับผลคูณสูงสุด เซตย่อยมีองค์ประกอบ- { -1,2,-5,2 }

สำหรับผลิตภัณฑ์ขั้นต่ำ เซตย่อยมีองค์ประกอบ- { 2,-5,2 }

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

• อาร์เรย์จำนวนเต็ม Arr[] ประกอบด้วยจำนวนเต็มบวกและลบ

• ขนาดตัวแปรประกอบด้วยความยาวของอาร์เรย์

• ฟังก์ชัน getProductSubset(int arr[], int n) รับอาร์เรย์เป็นอินพุตและส่งคืนผลิตภัณฑ์สูงสุดและต่ำสุดขององค์ประกอบที่ได้รับ

• ตัวแปร curMin, curMax ใช้เพื่อจัดเก็บผลิตภัณฑ์สูงสุดและต่ำสุดที่พบในปัจจุบัน เริ่มแรก arr[0].

• ตัวแปร prevMin, prevMax ใช้เพื่อจัดเก็บผลิตภัณฑ์สูงสุดและต่ำสุดก่อนหน้าที่พบ เริ่มแรก arr[0].

• ตัวแปร maxProd และ minProd ใช้เพื่อจัดเก็บผลิตภัณฑ์สูงสุดและต่ำสุดขั้นสุดท้ายที่ได้รับ

• เริ่มสำรวจอาร์เรย์จากองค์ประกอบที่ 2 arr[1] จนถึงดัชนีสุดท้าย

• สำหรับผลิตภัณฑ์สูงสุด ให้คูณ arr[i] ปัจจุบันด้วย prevMax และ prevMin จัดเก็บผลิตภัณฑ์สูงสุดใน curMax หากเป็น curMax>prevMax ให้อัปเดต curMax ด้วย prevMax

• อัปเดต maxProd ด้วย curMax ถ้า curMax>maxProd

• ที่ล่าสุดอัปเดต prevMax ด้วย curMax สำหรับการทำซ้ำครั้งต่อไป

• ทำตามขั้นตอนเดียวกับด้านบนสำหรับ prevMin, curMin และ minProd โดยเปลี่ยนการเปรียบเทียบ

• พิมพ์ผลลัพธ์ที่ได้รับใน maxProd และ minProd หลังจากสิ้นสุดการวนซ้ำ

ตัวอย่าง

#include <iostream>
using namespace std;
void getProductSubset(int arr[], int n){
   // Initialize all products with arr[0]
   int curMax = arr[0];
   int curMin = arr[0];
   int prevMax = arr[0];
   int prevMin= arr[0];
   int maxProd = arr[0];
   int minProd = arr[0];
   int temp1=0,temp2=0,temp3=0;
   // Process all elements after arr[0]
   for (int i = 1; i < n; ++i){
      /* Current maximum product is maximum of following
      1) prevMax * current arr[i] (when arr[i] is +ve)
      2) prevMin * current arr[i] (when arr[i] is -ve)
      3) current arr[i]
      4) Previous max product */
      temp1=prevMax*arr[i];
      temp2=prevMin*arr[i];
      temp3=temp1>temp2?temp1:temp2;
      curMax = temp3>arr[i]?temp3:arr[i];
      curMax = curMax>prevMax?curMax:prevMax;
      /* Current minimum product is minimum of following
      1) prevMin * current arr[i] (when arr[i] is +ve)
      2) prevMax * current arr[i] (when arr[i] is -ve)
      3) current arr[i]
      4) Previous min product */
      temp1=prevMax*arr[i];
      temp2=prevMin*arr[i];
      temp3=temp1<temp2?temp1:temp2;
      curMin = temp3<arr[i]?temp3:arr[i];
      curMin = curMin<prevMin?curMin:prevMin;
      maxProd = maxProd>curMax?maxProd:curMax;
      minProd = minProd<curMin?minProd:curMin;
      // copy current values to previous values
      prevMax = curMax;
      prevMin = curMin;
   }
   std::cout<<"Maximum Subset Product: "<<maxProd;
   std::cout<<"\nMinimum Subset Product: "<<minProd;
}
int main(){
   int Arr[] = {-4, -3, 1, 2, 0, 8, 1};
   // int arr[] = {-4, 1,1, 3, 5,7};
   int size = 7;
   getProductSubset(Arr,size ) ;
   return 0;
}

ผลลัพธ์

Maximum Subset Product: 192
Minimum Subset Product: -64