ซับเซ็ตผลคูณสูงสุดของอาร์เรย์ในโปรแกรม C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ของค่าจำนวนเต็ม n ค่า ภารกิจของเราคือสร้างโปรแกรมเพื่อหาซับเซ็ตผลคูณสูงสุดของอาร์เรย์

คำอธิบายปัญหา

ที่นี่ เราต้องคำนวณผลคูณสูงสุดที่เป็นไปได้ของซับเซ็ตขององค์ประกอบของอาร์เรย์

ซับเซ็ต (Subset) - อาร์เรย์ sub[] เป็นซับเซ็ตของอาร์เรย์ arr[] หากองค์ประกอบทั้งหมดของ sub[] อยู่ใน arr[]

ตัวอย่าง

อินพุต

arr[] = {4, 5, 2, -1, 3}

เอาต์พุต

40

คำอธิบาย

ซับเซ็ต sub[] = {4, 5, 2} 
Prod = 4*5*2 = 40

แนวทางแก้ปัญหา

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

วิธีนี้ง่ายต่อการนำไปใช้แต่ต้องการลูปซ้อนทำให้ความซับซ้อนอยู่ที่ออเดอร์ O(n²*n)

วิธีแก้ที่มีประสิทธิภาพ คือการคำนวณจำนวนค่าลบ (nofNeg) และศูนย์ (nof0) จากอาร์เรย์ แล้วคำนวณ maxProd ตามเงื่อนไขเหล่านี้

กรณีที่ 1 (nof0 = 0 และ nofNeg เป็นคู่) - พิจารณาองค์ประกอบทั้งหมดของอาร์เรย์สำหรับผลคูณ

maxProd = arr[0] * arr[1] * … arr[n-1]

กรณีที่ 2 (nof0 = 0 และ nofNeg เป็นคี่) - พิจารณาองค์ประกอบทั้งหมดยกเว้นองค์ประกอบลบที่ใหญ่ที่สุดของอาร์เรย์ (ใกล้ 0 มากที่สุด)

กรณีที่ 3 (nof0 != 0) - ทิ้งศูนย์ทั้งหมดของอาร์เรย์สำหรับผลคูณ และใช้กรณีคล้ายกรณี 1 และ 2

กรณีพิเศษ - มีเพียงหนึ่งองค์ประกอบที่ไม่ใช่ศูนย์เป็นลบ maxProd = 0

อัลกอริทึม

เริ่มต้น

maxProd = 1;

ขั้นตอนที่ 1

วนลูปอาร์เรย์และนับ nof0(จำนวนศูนย์) และ nofNeg(จำนวนลบ) และหา maxProd maxProd = maxProd*arr[i], i → 0 ถึง n-1

ขั้นตอนที่ 2

พิจารณากรณีต่อไปนี้ - 
กรณี 1 ถ้า (nofNeg%2 == 0): maxProd 
กรณี 2 ถ้า (nofNeg%2 != 0): maxProd = maxProd/(largestNeg) 
กรณี 3 ถ้า (nof0 == (n-1) and nofNeg == 1), maxProd = 0

ขั้นตอนที่ 3

พิมพ์ maxProd

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

โปรแกรมสำหรับแสดงการทำงานของวิธีแก้ปัญหาของเรา

#include <iostream> 
using namespace std; 

int findMaxSubsetProd(int arr[], int n){ 
    int larNeg = -1000; 
    int nofNeg = 0, Nof0 = 0; 
    int maxProd = 1; 
    for (int i = 0; i < n; i++) { 
        if (arr[i] == 0){ 
            Nof0++; 
            continue; 
        } 
        else if (arr[i] < 0) { 
            nofNeg++; 
            if(larNeg < arr[i]) 
                larNeg = arr[i]; 
        } 
        maxProd = maxProd * arr[i]; 
    } 
    if(nofNeg%2 == 0){ 
        return maxProd; 
    } 
    else if(nofNeg%2 != 0) 
        return (maxProd / larNeg); 
    if(Nof0 == (n-1) and nofNeg == 1) 
        return 0; 
    return maxProd; 
} 

int main(){ 
    int arr[] = {4, -2, 5, -1, 3, -6}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    cout << "The maximum product subset of an array is " << findMaxSubsetProd(arr, n); 
    return 0; 
}

เอาต์พุต

The maximum product subset of an array is 720