資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
時尚研究
法律研究最大乘積子陣列——在 C++ 中使用兩次遍歷
在該問題中，我們給出了一個整數陣列 arr[]。我們的任務是建立一個程式，在 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）的最大乘積。另一個用於計算從右到左的遍歷（即從索引 n-1 到 0）的最大乘積。該演算法的其餘部分與尋找最大乘積子陣列相同。
用於說明我們解決方案的工作原理的程式，
示例
#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
更新時間：2020 年 9 月 15 日
143 次瀏覽
廣告