ผลคูณสูงสุดของเซิร์บซีเควลขนาด k ใน C++

ปัญหา

ในปัญหานี้ เราได้รับอาร์เรย์ 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 (ถ้าค่าสูงสุดเป็นบวก) - หมายความว่าอาร์เรย์ผสมบวกและลบ ในกรณีนี้ เราจะหาค่าสูงสุด k ตัวและค้นหาคู่สูงสุดจากด้านลบ (ถ้าเป็นไปได้อาจให้ผลลัพธ์)

กรณี 2.2 (ถ้าค่าสูงสุดเป็นศูนย์) - หมายความว่าอาร์เรย์มีแค่ค่าลบและศูนย์ ในกรณีนี้ ผลลัพธ์สูงสุดจะเป็น 0 เนื่องจากคูณจำนวนคี่ของค่าลบจะได้ค่าลบ ซึ่ง 0 คือผลคูณสูงสุด

กรณี 2.3 (ถ้าค่าสูงสุดเป็นลบ) - หมายความว่าอาร์เรย์มีแค่ค่าลบ ในกรณีนี้ ผลลัพธ์สูงสุดจะได้จากการคูณสมาชิกที่มีขนาดน้อยที่สุด คือค่าสูงสุดของอาร์เรย์จะช่วยได้

ด้วยวิธีนี้ เราต้องตรวจสอบค่าของสมาชิกและ k สำหรับผลลัพธ์ที่เหมาะสมที่สุด สำหรับนี้ เราจะเก็บค่าสูงสุดและต่ำสุดทั้งสองด้านในอาร์เรย์เพื่อตรวจสอบว่าผลลัพธ์สามารถได้จากการคูณคู่ลบหรือไม่

ตัวอย่างโค้ด

โปรแกรมแสดงการทำงานของคำตอบของเรา

#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