資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++程式中的陣列最大乘積子集
在這個問題中，我們得到一個包含n個整數值的陣列arr[]。我們的任務是建立一個程式來查詢陣列的最大乘積子集。
問題描述 − 在這裡，我們需要計算陣列元素子集的最大可能乘積。
子集 − 如果子集sub[]中的所有元素都存在於陣列arr[]中，則sub[]是arr[]的子集。
讓我們來看一個例子來理解這個問題：
輸入
arr[] = {4, 5, 2, −1, 3}輸出
40
解釋
Subset sub[] = {4, 5, 2}
Prod = 4*5*2 = 40解決方案方法
解決這個問題的一個簡單易行的方法是建立陣列的所有可能的子集。找到它們的乘積並返回其中的最大值。
這種解決方案易於實現，但需要巢狀迴圈，使其複雜度為O(n2*n)。
有效的解決方案是透過計算陣列中負數(nofNeg)和零(nof0)的個數，然後根據這些條件計算maxProd。
情況1(nof0 = 0且nofNeg為偶數) - 將陣列的所有元素考慮在乘積中。
maxProd = arr[0] * arr[1] * … arr[n−1]
情況2(nof0 = 0且nofNeg為奇數) - 考慮陣列中的所有元素，除了陣列中最大的負元素（最接近0的）。
情況3(nof0 != 0) - 將陣列的所有零排除在乘積之外。並採取與情況1和2類似的情況。
特殊情況 - 只有一個元素（除了0）是負數。maxProd = 0。
演算法
初始化 −
maxProd = 1;
步驟1 −
Loop the array and count, nof0(number of zeros) and nofNeg(number of negatives), and find maxProd. maxProd = maxProd*arr[i], i −> 0 to n−1
步驟2 −
consider the following cases − Case 1− if(nofNeg%2 == 0): maxProd Case 2− if(nofNeg%2 != 0): maxProd = maxProd/(largestNeg) Case 3 − if(nof0 == (n-1) and nofNeg == 1), maxProd = 0.
步驟3
Print maxProd.
示例
程式說明了我們解決方案的工作原理：
#include <iostream>
using namespace std;
int findMaxSubsetProd(int arr[], int n){
int larNeg = −1000;
int nofNeg = 0, Nof0 = 0;
int maxProd = 1;
for (int i = 0; i < n; i++) {
if (arr[i] == 0){
Nof0++;
continue;
}
else if (arr[i] < 0) {
nofNeg++;
if(larNeg < arr[i])
larNeg = arr[i];
}
maxProd = maxProd * arr[i];
}
if(nofNeg%2 == 0){
return maxProd;
}
else if(nofNeg%2 != 0)
return (maxProd / larNeg);
if(Nof0 == (n−1) and nofNeg == 1)
return 0;
return maxProd;
}
int main(){
int arr[] = {4, −2, 5, −1, 3, −6};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The maximum product subset of an array is "<<findMaxSubsetProd(arr, n);
return 0;
}輸出
The maximum product subset of an array is 720
更新於：2020年12月9日
183 次瀏覽
廣告