資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告