การหาผลคูณสูงสุดและต่ำสุดของเซตย่อยใน C++

เราได้รับอาร์เรย์ของจำนวนเต็มขนาด N เป้าหมายคือการหาผลคูณสูงสุดและต่ำสุดของเซตย่อย (Subset) เราจะทำได้โดยใช้ตัวแปรผลคูณสองตัว: 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[] มีจำนวนเต็มบวกและลบ
• ตัวแปร size เก็บขนาดอาร์เรย์
• ฟังก์ชัน getProductSubset(int arr[], int n) รับอาร์เรย์และคืนค่าผลคูณสูงสุดและต่ำสุด
• ตัวแปร curMin, curMax เก็บผลคูณต่ำสุดและสูงสุดปัจจุบัน เริ่มต้นที่ arr[0]
• ตัวแปร prevMin, prevMax เก็บผลคูณต่ำสุดและสูงสุดก่อนหน้า เริ่มต้นที่ arr[0]
• ตัวแปร maxProd และ minProd เก็บผลคูณสูงสุดและต่ำสุดสุดท้าย
• เริ่มวนลูปจากสมาชิกที่สอง 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) {
    // เริ่มต้นทุกผลคูณด้วย 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;
    
    // ประมวลผลสมาชิกหลัง arr[0]
    for (int i = 1; i < n; ++i) {
        /* ผลคูณสูงสุดปัจจุบัน คือค่าสูงสุดของ:
           1) prevMax * arr[i] (เมื่อ arr[i] เป็นบวก)
           2) prevMin * arr[i] (เมื่อ arr[i] เป็นลบ)
           3) arr[i] เอง
           4) ผลคูณสูงสุดก่อนหน้า */
        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;
        
        /* ผลคูณต่ำสุดปัจจุบัน คือค่าต่ำสุดของ:
           1) prevMin * arr[i] (เมื่อ arr[i] เป็นบวก)
           2) prevMax * arr[i] (เมื่อ arr[i] เป็นลบ)
           3) arr[i] เอง
           4) ผลคูณต่ำสุดก่อนหน้า */
        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;
        
        // คัดลอกค่าปัจจุบันไปเป็นค่าก่อนหน้า
        prevMax = curMax;
        prevMin = curMin;
    }
    cout << "Maximum Subset Product: " << maxProd;
    cout << "\nMinimum Subset Product: " << minProd;
}

int main() {
    int Arr[] = {-4, -3, 1, 2, 0, 8, 1};
    int size = 7;
    getProductSubset(Arr, size);
    return 0;
}

ผลลัพธ์

Maximum Subset Product: 192 Minimum Subset Product: -64