이 문제에서는 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)
따라서 배열을 순회하여 이러한 값을 직접 찾을 수 있으며 값을 사용하여 최대 곱 삼중항을 찾을 수 있습니다.
알고리즘
초기화
최대 =-1000, secMax =-1000, thirdMax =-1000, 최소 =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