이 문제에서는 배열 arr[]이 제공됩니다. 우리의 임무는 C++의 배열에서 최대 곱 4배(크기 4의 하위 시퀀스)를 찾는 프로그램을 만드는 것입니다.
코드 설명 − 여기에서 모든 요소의 곱이 최대가 되도록 4배(크기 4의 부분 수열)를 찾아야 합니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력
arr[] = {4, -2, 5, -6, 8} 출력
840
설명
쿼드러플(-3, 5, -7, 8)과 제품 840.
해결 방법
주어진 문제에 대해 여러 가지 해결책이 있을 수 있습니다.
한 가지 간단한 솔루션은 배열을 순회하여 직접 방법을 사용하는 것입니다. 그런 다음 배열에서 가능한 모든 4배를 찾습니다. 제품을 찾은 다음 비교하여 최대 제품을 4배로 찾습니다.
우리 솔루션의 작동을 설명하는 프로그램
예
#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
최대 곱으로 4배를 찾는 또 다른 방법은 배열의 최대 4개 요소와 배열의 최소 4개 요소를 찾는 것입니다.
mx1, mx2, mx3, mx4가 처음 4개의 최대 숫자라고 가정해 보겠습니다. 그리고 mn1, mn2, mn3, mn4는 배열의 처음 4개 최소값입니다. 그런 다음
의 값을 찾으십시오.1. mx1 * mx2 * mx3 * mx4 2. mn1 * mn2 * mn3 * mn4 3. mx1 * mx2 * mn1 * mn2
그리고 이 세 가지 제품 값의 최대값을 반환하여 최대 제품을 4배로 만듭니다. 그리고 모든 경우가 고려됩니다.
알고리즘 구현을 보여주는 프로그램
예
#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
또 다른 접근 방식은 배열을 정렬하는 것입니다. 그러면 4개의 최대값과 4개의 최소값이 각각 배열의 끝과 시작이 됩니다. 그런 다음 최대값과 최소값의 세 가지 조합 중 최대값을 구하여 위의 해와 같이 풉니다.
우리의 접근 방식의 구현을 보여주는 프로그램
예
#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