数据结构
网络
关系数据库管理系统 (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 次查看
广告