ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ของจำนวนเต็ม งานของเราคือสร้างโปรแกรมเพื่อค้นหา Subarray ของผลิตภัณฑ์สูงสุด - โดยใช้ Two Traversalsin C++
คำอธิบายปัญหา - ในอาร์เรย์ เราจะพบอาร์เรย์ย่อยของผลิตภัณฑ์สูงสุดโดยใช้การข้ามผ่านสองครั้งระหว่างดัชนี 0 และดัชนีอื่น (n-1)
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
arr[] = {4, -2, 5, -6, 0, 8} ผลลัพธ์
240
ตัวอย่าง
Subarray = {4, -2, 5, -6}
Maximum product = 4 * (-2) * 5 * (-6) = 240 แนวทางการแก้ปัญหา
เพื่อแก้ปัญหานี้โดยใช้การข้ามผ่านสองครั้ง ที่นี่ เราจะค้นหาค่าสูงสุดของผลิตภัณฑ์โดยใช้ค่าสูงสุดในพื้นที่สองค่าสำหรับการข้ามผ่านจากซ้ายไปขวา เช่น จากดัชนี 0 ถึง n-1 และอีกอันหนึ่งสำหรับการข้ามจากขวาไปซ้าย เช่น จาก indexn-1 ถึง 0 อัลกอริธึมที่เหลือจะเหมือนกับการค้นหา productubarray สูงสุด
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include<iostream>
using namespace std;
int CalcMaxProductSubArray(int arr[], int n) {
int frntMax = 1, rearMax = 1, maxVal = 1;
for (int i=0; i<n; i++) {
frntMax = frntMax*arr[i];
if (frntMax == 0)
frntMax = 1;
}
for (int i=n-1; i>=0; i--) {
rearMax = rearMax * arr[i];
if (rearMax == 0)
rearMax = 1;
}
maxVal = max(frntMax, rearMax);
return maxVal;
}
int main() {
int arr[] = {4, -2, 5, -6, 0, 8};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"Maximum product subarray is "<<CalcMaxProductSubArray(arr, n);
return 0;
} ผลลัพธ์
Maximum product subarray is 240
