ในปัญหานี้ เราได้รับอาร์เรย์ของจำนวนเต็ม (บวกและลบ) งานของเราคือสร้างโปรแกรมเพื่อคำนวณ Maximum ProductSubarray ใน 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
