資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++程式中陣列中三元組（大小為3的子序列）的最大乘積。
在這個問題中，我們得到一個包含n個整數的陣列arr[]。我們的任務是找到陣列中三元組（大小為3的子序列）的最大乘積。我們將找到乘積值最大的三元組，然後返回該乘積。
讓我們舉個例子來理解這個問題：
輸入
arr[] = {9, 5, 2, 11, 7, 4}輸出
693
解釋
這裡，我們將找到產生陣列所有元素最大乘積的三元組。maxProd = 9 * 11 * 7 = 693
解決方案方法
這個問題可能有不止一種解決方案。我們將在這裡討論它們：
方法1
直接方法 在這種方法中，我們將直接遍歷陣列，然後找到所有可能的三元組。找到每個三元組元素的乘積，並返回所有乘積中的最大值。
演算法
初始化
maxProd = −1000
步驟1:
Create three nested loops: Loop 1:i −> 0 to n−3 Loop 2: j −> i to n−2 Loop 3: k −> j to n−1
步驟1.1 −
Find the product, prod = arr[i]*arr[j]*arr[k].
步驟1.2 −
if prod > maxProd −> maxProd = prod.
步驟3 −
return maxProd.
示例
程式演示了我們解決方案的實現：
#include <iostream>
using namespace std;
int calcMaxProd(int arr[], int n){
int maxProd = −1000;
int prod;
for (int i = 0; i < n − 2; i++)
for (int j = i + 1; j < n − 1; j++)
for (int k = j + 1; k < n; k++){
prod = arr[i] * arr[j] * arr[k];
if(maxProd < prod)
maxProd = prod;
}
return maxProd;
}
int main(){
int arr[] = { 9, 5, 2, 11, 7, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum product of a triplet in array is "<<calcMaxProd(arr, n);
return 0;
}輸出
Maximum product of a triplet in array is 693
方法2
使用排序
在這種方法中，我們將陣列按降序排序。在排序後的陣列中，最大乘積的三元組將位於：
(arr[0], arr[1], arr[2]) (arr[0], arr[1], arr[2])
我們將返回這些三元組乘積的最大值。
演算法
步驟1 −
Sort the given array in descending order.
步驟2 −
Find product of triples, maxTriplet1 = arr[0]*arr[1]*arr[2] maxTriplet2 = arr[0]*arr[n−1]*arr[n−2]
步驟3 −
if( maxTriplet1 > maxTriplet2 ) −> return maxTriplet1
步驟4 −
else −> return maxTriplet2.
示例
程式說明了我們解決方案的工作原理：
#include <bits/stdc++.h>
using namespace std;
int calcMaxProd(int arr[], int n){
sort(arr, arr + n, greater<>());
int maxTriplet1 = arr[0]*arr[1]*arr[2];
int maxTriplet2 = arr[0]*arr[n−1]*arr[n−2];
if(maxTriplet1 > maxTriplet2)
return maxTriplet1;
return maxTriplet2;
}
int main(){
int arr[] = { 9, 5, 2, 11, 7, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum product of a triplet in array is
"<<calcMaxProd(arr, n);
return 0;
}輸出
陣列中三元組的最大乘積是693
方法3
查詢三元組值。
正如我們現在所知，最大乘積的三元組可以來自兩個三元組中的任何一個：
(maximum, second_max, third_max) (maximum, minimum, second_min)
因此，我們可以透過遍歷陣列直接找到這些值，然後使用這些值找到最大乘積的三元組。
演算法
初始化
max = -1000, secMax = -1000, thirdMax = -1000 , min = 10000, secMin = 10000
步驟1−
loop the array i −> 0 to n−1.
步驟1.1
if(arr[i] > max) −> thirdMax = secMax, secMax = max, max = arr[i]
步驟1.2−
elseif(arr[i] > secMax) −> thirdMax = secMax, secMax = arr[i]
步驟1.3−
elseif(arr[i] > thirdMax) −> thirdMax = arr[i]
步驟1.4−
if(arr[i] < min) −> secMin = min, min = arr[i]
步驟1.4−
elseif(arr[i] < secMin) −> secMin = arr[i]
步驟2−
triplet1 = max * secMax * thridMax triplet2 = max * min * secMin
步驟3−
if(triplet1 > triplet2) −> return triplet1
步驟4−
else −> return triplet2
示例
程式說明了我們解決方案的工作原理：
#include <iostream>
using namespace std;
int calcMaxProd(int arr[], int n){
int max = −1000, secMax = −1000, thirdMax = −1000;
int min = 1000, secMin = 1000;
for (int i = 0; i < n; i++){
if (arr[i] > max){
thirdMax = secMax;
secMax = max;
max = arr[i];
}
else if (arr[i] > secMax){
thirdMax = secMax;
secMax = arr[i];
}
else if (arr[i] > thirdMax)
thirdMax = arr[i];
if (arr[i] < min){
secMin = min;
min = arr[i];
}
else if(arr[i] < secMin)
secMin = arr[i];
}
int triplet1 = max * secMax * thirdMax;
int triplet2 = max * secMin * min;
if(triplet1 > triplet2)
return triplet1;
return triplet2;
}
int main(){
int arr[] = { 9, 5, 2, 11, 7, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum product of a triplet in array is
"<<calcMaxProd(arr, n);
return 0;
}輸出
Maximum product of a triplet in array is 693
更新於：2020年12月9日
477 次檢視
廣告