ผลคูณสูงสุดของเซิร์บอาร์เรย์ | เพิ่มกรณีผลคูณลบใน C++

ปัญหา

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

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

ตัวอย่าง

มาดูตัวอย่างเพื่อเข้าใจปัญหา

อินพุต

arr[] = {-1, 2, -7, -5, 12, 6}

เอาต์พุต

5040

คำอธิบาย

เซิร์บอาร์เรย์ที่มีผลคูณสูงสุดคือ {2, -7, -5, 12, 6}

Product = 5040

วิธีแก้ปัญหา

เพื่อแก้ปัญหานี้ เราได้รับอาร์เรย์และผลคูณสูงสุดของเซิร์บอาร์เรย์และจัดการ maxVal ซึ่งคือผลคูณสูงสุดจนถึงสมาชิกปัจจุบัน และ minVal คือค่าลบสูงสุดของผลคูณ จากนั้นตามค่าปัจจุบัน maxVal และ minVal จะถูกอัปเดตดังนี้:

กรณี 1 - สมาชิกเป็นบวก - อัปเดต maxVal และ minVal โดยการคูณกับอาร์เรย์

กรณี 2 - สมาชิกเป็นศูนย์ - หยุดเซิร์บอาร์เรย์ปัจจุบัน เพราะคูณด้วย 0 จะได้ 0

กรณี 3 - สมาชิกเป็นลบ - อัปเดตทั้งสองค่าด้วยค่าลบ ทำให้เป็นค่าสูงสุด

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

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

#include <iostream> 
using namespace std; 

int min(int a, int b){ 
    if(a < b) 
        return a; 
    return b; 
} 

int max(int a, int b){ 
    if(a > b) 
        return a; 
    return b; 
} 

int CalcMaxProductSubArray(int arr[], int n) { 
    int i = 0; 
    int maxVal = -1000; 
    int localMax = 1; 
    int localMin = 1; 
    int lastMax; 
    while(i < n) { 
        int currentVal = arr[i]; 
        if (currentVal > 0) { 
            localMax = (localMax * currentVal); 
            localMin = min(1, localMin * currentVal); 
        } 
        else if (currentVal < 0) { 
            lastMax = localMax; 
            localMax = (localMin * currentVal); 
            localMin = (lastMax * currentVal); 
        } else { 
            localMin = 1; 
            localMax = 0; 
        } 
        maxVal = max(maxVal, localMax); 
        if (localMax <= 0) 
            localMax = 1; 
        i++; 
    } 
    return maxVal; 
} 

int main(){ 
    int arr[] = { -1, 2, -7, -5, 12, 6 }; 
    int n = 6; 
    cout<<"The maximum product Subarray is "<<CalcMaxProductSubArray(arr, n); 
    return 0; 
}

เอาต์พุต

The maximum product Subarray is 5040