資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝學
法學最大乘積子陣列 | 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
更新於：2020年9月15日
瀏覽量 125 次
廣告