C ++程序数组中三元组（大小为3的子序列）的最大乘积。
在这个问题中，我们得到了一个由n个整数组成的数组arr []。我们的任务是找到数组中三元组（大小为3的子序列）的最大乘积。在这里，我们将找到具有最大产品价值的三元组，然后退还产品。
让我们举个例子来了解这个问题，
输入项
arr[] = {9, 5, 2, 11, 7, 4}输出结果
693
说明
在这里，我们将找到三元组，该三元组给出了数组所有元素的最大乘积。maxProd = 9 * 11 * 7 = 693
解决方法
该问题可以有多种解决方案。我们将在这里讨论它们，
方法1
直接方法在此方法中，我们将直接遍历数组，然后查找所有可能的三元组。查找每个三元组元素的乘积，然后返回所有元素的最大值。
算法
初始化
maxProd = −1000
第一步：
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<<"数组中三元组的最大乘积为 "<<calcMaxProd(arr, n);
return 0;
}
输出结果
数组中三元组的最大乘积为 693
方法二
使用排序
在此方法中，我们将按降序对数组进行排序。在排序数组中，最大三元乘积将为
(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<<"数组中三元组的最大乘积为
"<<calcMaxProd(arr, n);
return 0;
}
输出结果
三元组数组的最大乘积为693
方法3
查找三元组值。
现在我们知道最大的三元组可以来自两个三元组中的一个
(maximum, second_max, third_max)(maximum, minimum, second_min)
因此，我们可以通过遍历数组直接找到这些值，然后使用这些值，我们将找到最大乘积三元组。
算法
初始化
最大值= -1000，秒最大值= -1000，第三最大值= -1000，最小值= 10000，秒最小值= 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 * thridMaxtriplet2 = 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<<"数组中三元组的最大乘积为
"<<calcMaxProd(arr, n);
return 0;
}
输出结果
数组中三元组的最大乘积为 693
以上是 C ++程序数组中三元组（大小为3的子序列）的最大乘积。 的全部内容， 来源链接： utcz.com/z/321480.html
