ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ของจำนวนเต็มและตัวเลข k งานของเราคือสร้างโปรแกรมเพื่อค้นหาผลคูณสูงสุดของลำดับย่อยของขนาด k ใน C ++
คำอธิบายปัญหา − ในที่นี้ เราต้องหาลำดับย่อยของขนาด k, 1<=k <=n ซึ่งมีผลคูณสูงสุดขององค์ประกอบ
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
arr[] = {1, 5, 6, -2, 0, 4} , k = 3 ผลลัพธ์
120
คำอธิบาย
ลำดับรองของขนาด 3 ที่มีผลผลิตสูงสุดคือ (5, 6, 4) สินค้าราคา 120.
แนวทางการแก้ปัญหา
ในการแก้ปัญหานี้ ก่อนอื่นเราจะเรียงลำดับอาร์เรย์ arr[] จากนั้นอิงตามองค์ประกอบของ arr[] และค่าของ k วิธีการเปลี่ยนในกรณีต่อไปนี้ -
กรณีที่ 1 (ถ้า k เป็นคู่) − ผลิตภัณฑ์สามารถมีค่า k สูงสุดได้ทั้งหมด ยกเว้น 0 ในที่นี้ เราต้องพิจารณาคู่ค่าลบด้วย เนื่องจากขนาดของมันยังสามารถให้ผลลัพธ์สูงสุดได้อีกด้วย
กรณีที่ 2 (ถ้า k เป็นเลขคี่) − นี่เป็นเงื่อนไขที่ซับซ้อนเล็กน้อย และค่ากำหนดวิธีการคำนวณผลลัพธ์ที่ต้องการ กรณีนี้จำเป็นต้องจัดประเภทเพิ่มเติมตามองค์ประกอบสูงสุดของอาร์เรย์
กรณีที่ 2.1 (ถ้าจำนวนสูงสุดเป็นบวก) − นี่หมายความว่าอาร์เรย์ประกอบด้วยจำนวนบวกและลบผสมกัน ในกรณีนี้ เราจะค้นหาองค์ประกอบ max k และค้นหาคู่สูงสุดจากด้านลบด้วย (หากเป็นไปได้ อาจให้ผลลัพธ์)
กรณีที่ 2.2 (ถ้าจำนวนสูงสุดเป็นศูนย์) − นี่หมายความว่าอาร์เรย์ประกอบด้วยองค์ประกอบเชิงลบทั้งหมดและเป็นศูนย์ ในกรณีนี้ ผลลัพธ์สูงสุดจะเป็น 0 เนื่องจากการคูณองค์ประกอบลบจำนวนคี่จะส่งผลให้เป็นจำนวนลบ ซึ่งหมายความว่า 0 คือผลคูณสูงสุด
กรณีที่ 2.3 (หากจำนวนสูงสุดเป็นค่าลบ) − นี่หมายความว่าอาร์เรย์ประกอบด้วยตัวเลขติดลบเท่านั้น ในกรณีนี้ ผลลัพธ์สูงสุดจะได้รับจากการคูณองค์ประกอบที่มีขนาดต่ำสุด เช่น อาร์เรย์สูงสุดจะช่วยได้
ด้วยวิธีนี้ เราต้องคอยตรวจสอบค่าขององค์ประกอบตลอดจน k เพื่อผลลัพธ์ที่ดีที่สุด สำหรับสิ่งนี้ เราจะเก็บค่า max และ min ทั้งสองข้างเป็น inarray เพื่อตรวจสอบว่าผลลัพธ์สามารถหาได้จากการคูณคู่ลบกับผลลัพธ์หรือไม่
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int findMaxSubArrayProduct(int arr[], int n, int k) {
sort(arr, arr + n);
int maxProd = 1;
int i = 0, j = 0;
int maxprod, minprod;
if (arr[n - 1] == 0 && (k % 2 == 1))
return 0;
if (arr[n - 1] <= 0 && (k % 2 == 1)) {
for (i = n - 1; i >= n - k; i--)
maxProd *= arr[i];
return maxProd;
}
i = 0;
j = n - 1;
if (k % 2 == 1) {
maxProd *= arr[j];
j--;
k--;
}
k = k/2;
int it = 0;
while(it < k){
int minprod = arr[i] * arr[i + 1];
int maxprod = arr[j] * arr[j - 1];
if (minprod > maxprod) {
maxProd *= minprod;
i += 2;
} else {
maxProd *= maxprod;
j -= 2;
}
it++;
}
return maxProd;
}
int main() {
int arr[] = { 1, 5, 6, -2, 0, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout<<"The maximum product of subsequence of size "<<k<<" is "<<findMaxSubArrayProduct(arr, n, k);
return 0;
} ผลลัพธ์
The maximum product of subsequence of size 3 is 120
