資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中的最大和最小乘積子集
給定一個大小為N的整數陣列。這裡的目標是找到最大和最小乘積子集。我們將透過使用兩個乘積變數來實現這一點，一個用於迄今為止找到的最小乘積`minProd`，另一個用於迄今為止找到的最大乘積`maxProd`。
在遍歷陣列時，我們將每個元素分別與`minProd`和`maxProd`相乘。還要檢查之前的最大乘積、之前的最小乘積、當前最大乘積、當前最小乘積以及當前元素本身。
輸入
Arr[]= { 1,2,5,0,2 }輸出
Maximum Product: 20 Minimum Product: 0
解釋 − 從陣列中的第二個元素開始，`maxProd`和`minProd`的值初始化為1（第一個元素）。
Arr[1]: 1*2=2, 1*2=2, maxProd=2, minProd=1 Arr[2]: 2*5=10, 1*5=5, maxProd=10, minProd=1 Arr[3]: 10*0=0, 1*0=0, maxProd=10, minProd=0 Arr[4]: 10*2=20, 0*2=0, maxProd=20, minProd=0
輸入
Arr[]= { -1,2,-5,0,2 }輸出
Maximum Product: 20 Minimum Product: -20
解釋 − 對於最大乘積，子集的元素為{-1, 2, -5, 2}
對於最小乘積，子集的元素為{2, -5, 2}
下面程式中使用的方法如下
整數陣列`Arr[]`包含正整數和負整數。
變數`size`包含陣列的長度。
函式`getProductSubset(int arr[], int n)`以陣列作為輸入，並返回獲得的元素的最大和最小乘積。
變數`curMin`、`curMax`用於儲存當前找到的最大和最小乘積。初始值為`arr[0]`。
變數`prevMin`、`prevMax`用於儲存先前找到的最大和最小乘積。初始值為`arr[0]`。
變數`maxProd`和`minProd`用於儲存最終獲得的最大和最小乘積。
從第二個元素`arr[1]`開始遍歷陣列，直到最後一個索引。
對於最大乘積，將當前`arr[i]`與`prevMax`和`prevMin`相乘。將最大乘積儲存在`curMax`中。如果`curMax > prevMax`，則用`prevMax`更新`curMax`。
如果`curMax > maxProd`，則用`curMax`更新`maxProd`。
最後，為下一次迭代將`prevMax`更新為`curMax`。
透過更改比較，對`prevMin`、`curMin`和`minProd`執行與上述相同的步驟。
迴圈結束後，列印`maxProd`和`minProd`中獲得的結果。
示例
#include <iostream>
using namespace std;
void getProductSubset(int arr[], int n){
// Initialize all products with arr[0]
int curMax = arr[0];
int curMin = arr[0];
int prevMax = arr[0];
int prevMin= arr[0];
int maxProd = arr[0];
int minProd = arr[0];
int temp1=0,temp2=0,temp3=0;
// Process all elements after arr[0]
for (int i = 1; i < n; ++i){
/* Current maximum product is maximum of following
1) prevMax * current arr[i] (when arr[i] is +ve)
2) prevMin * current arr[i] (when arr[i] is -ve)
3) current arr[i]
4) Previous max product */
temp1=prevMax*arr[i];
temp2=prevMin*arr[i];
temp3=temp1>temp2?temp1:temp2;
curMax = temp3>arr[i]?temp3:arr[i];
curMax = curMax>prevMax?curMax:prevMax;
/* Current minimum product is minimum of following
1) prevMin * current arr[i] (when arr[i] is +ve)
2) prevMax * current arr[i] (when arr[i] is -ve)
3) current arr[i]
4) Previous min product */
temp1=prevMax*arr[i];
temp2=prevMin*arr[i];
temp3=temp1<temp2?temp1:temp2;
curMin = temp3<arr[i]?temp3:arr[i];
curMin = curMin<prevMin?curMin:prevMin;
maxProd = maxProd>curMax?maxProd:curMax;
minProd = minProd<curMin?minProd:curMin;
// copy current values to previous values
prevMax = curMax;
prevMin = curMin;
}
std::cout<<"Maximum Subset Product: "<<maxProd;
std::cout<<"\nMinimum Subset Product: "<<minProd;
}
int main(){
int Arr[] = {-4, -3, 1, 2, 0, 8, 1};
// int arr[] = {-4, 1,1, 3, 5,7};
int size = 7;
getProductSubset(Arr,size ) ;
return 0;
}輸出
Maximum Subset Product: 192 Minimum Subset Product: -64
瀏覽量：288
