数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中数组的最大乘积四元组（大小为4的子序列）
在这个问题中，我们得到一个数组arr[]。我们的任务是创建一个程序，在C++中查找数组中的最大乘积四元组（大小为4的子序列）。
代码描述 − 在这里，我们需要找到一个四元组（大小为4的子序列），使得所有元素的乘积最大。
让我们举个例子来理解这个问题：
输入
arr[] = {4, -2, 5, -6, 8}输出
840
解释
四元组 (-3, 5, -7, 8)，乘积为 840。
解决方案方法
一个给定问题可能有多种解决方案。
一个简单的解决方案是使用直接方法遍历数组。然后找到数组中所有可能的四元组。找到它们的乘积，然后进行比较以找到最大乘积四元组。
程序演示了我们解决方案的工作原理：
示例
#include <iostream>
using namespace std;
int max(int a, int b){
if(a > b)
return a;
return b;
}
int findMaxProdQuad(int arr[], int n){
int maxProd = 0;
int prod = 1;
for (int i = 0; i <= n - 4; i++)
for (int j = i + 1; j <= n - 3; j++)
for (int k = j + 1; k <= n - 2; k++)
for (int l = k + 1; l <= n - 1; l++) {
prod = arr[i] * arr[j] * arr[k] * arr[l];
maxProd = max(maxProd, prod);
prod = 1;
}
return maxProd;
}
int main(){
int arr[] = {4, -2, 5, -6, 8};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum product of quadruple is "<<findMaxProdQuad(arr, n);
return 0;
}输出
Maximum product of quadruple is 480
另一种找到乘积最大的四元组的方法是找到数组的四个最大元素和四个最小元素。
假设mx1、mx2、mx3、mx4是前四个最大数。mn1、mn2、mn3、mn4是数组的前四个最小数。然后找到以下值：
1. mx1 * mx2 * mx3 * mx4 2. mn1 * mn2 * mn3 * mn4 3. mx1 * mx2 * mn1 * mn2
并返回这三个乘积值的较大值，这将给出最大乘积四元组。并且考虑所有情况。
程序展示了我们算法的实现
示例
#include <iostream>
using namespace std;
int max(int a, int b){
if(a > b)
return a;
return b;
}
int findMaxProdQuad(int arr[], int n) {
int mx1 = -1000, mx2 = -1000, mx3 = -10000, mx4 = -1000;
int mn1 = 1000, mn2 = 1000, mn3 = 1000, mn4 = 1000;
for (int i = 0; i < n; i++) {
if(arr[i] < mn1){
mn4 = mn3;
mn3 = mn2;
mn2 = mn1;
mn1 = arr[i];
}
else if(arr[i] < mn2){
mn4 = mn3;
mn3 = mn2;
mn2 = arr[i];
}
else if(arr[i] < mn3){
mn4 = mn3;
mn3 = arr[i];
}
else if(arr[i] < mn4){
mn4 = arr[i];
}
if(arr[i] > mx1){
mx4 = mx3;
mx3 = mx2;
mx2 = mx1;
mx1 = arr[i];
}
else if(arr[i] > mx2){
mx4 = mx3;
mx3 = mx2;
mx2 = arr[i];
}
else if(arr[i] > mx3){
mx4 = mx3;
mx3 = arr[i];
}
else if(arr[i] > mx4){
mx4 = arr[i];
}
}
int maxVal = max ((mx1 * mx2 * mx3 * mx4), (mn1 * mn2 * mn3 * mn4));
maxVal = max(maxVal, (mx1 * mx2 * mn1 * mn2));
return maxVal;
}
int main() {
int arr[] = {4, -2, 5, -6, 8};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum product of quadruple is "<<findMaxProdQuad(arr, n);
return 0;
}输出
Maximum product of quadruple is 480
另一种方法是对数组进行排序。然后，四个最大值和四个最小值将分别位于数组的末尾和开头。然后像上面的解决方案一样，通过找到最大值和最小值的三个组合的最大值来求解。
程序展示了我们方法的实现
示例
#include <bits/stdc++.h>
using namespace std;
int findMaxProdQuad(int arr[], int n){
sort(arr, arr + n);
int maxVal = max((arr[n-1] * arr[n-2] * arr[n-3] * arr[n-4]), (arr[0] *
arr[1] * arr[2] * arr[3]));
maxVal = max(maxVal, (arr[n-1] * arr[n-2] * arr[0] * arr[1]));
return maxVal;
}
int main(){
int arr[] = {4, -2, 5, -6, 8};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum product of quadruple is "<<findMaxProdQuad(arr, n);
return 0;
}输出
Maximum product of quadruple is 480
更新于：2020年9月15日
316 次浏览
广告