Trong bài toán này, chúng ta được cung cấp một mảng arr [] các số nguyên. Nhiệm vụ của chúng tôi là tạo ra chương trình để tìm Mảng con sản phẩm tối đa - Sử dụng hai Traversalsin C ++.
Mô tả sự cố - Ở đây trong mảng, chúng ta sẽ tìm thấy mảng con sản phẩm tối đa bằng cách sử dụng hai truyền một từ chỉ mục 0 và một chỉ mục khác (n-1).
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {4, -2, 5, -6, 0, 8} Đầu ra
240
Ví dụ
Subarray = {4, -2, 5, -6}
Maximum product = 4 * (-2) * 5 * (-6) = 240 Phương pháp tiếp cận giải pháp
Để giải quyết vấn đề này bằng cách sử dụng hai đường truyền. Ở đây, chúng tôi sẽ tìm sản phẩm tối đa bằng cách sử dụng hai giá trị lớn nhất cục bộ cho truyền từ trái sang phải, tức là từ chỉ số 0 đến n-1. Và một để duyệt từ phải sang trái, tức là từ indexn-1 đến 0. Thuật toán còn lại giống như việc tìm kiếm các sản phẩm tối đa.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
Maximum product subarray is 240