문제에서 n개의 정수 값의 배열 arr[]이 제공됩니다. 우리의 임무는 어레이의 최대 곱 하위 집합을 찾는 프로그램을 만드는 것입니다.
문제 설명 − 여기에서 배열 요소의 하위 집합의 가능한 최대 곱을 계산해야 합니다.
하위 집합 - sub[]의 모든 요소가 arr[]에 있는 경우 배열 sub[]는 배열 arr[]의 하위 집합입니다.
문제를 이해하기 위해 예를 들어 보겠습니다.
입력
arr[] = {4, 5, 2, −1, 3} 출력
40
설명
Subset sub[] = {4, 5, 2}
Prod = 4*5*2 = 40 솔루션 접근 방식
문제를 해결하는 간단하고 쉬운 접근 방식은 배열의 모든 가능한 부분 집합을 만드는 것입니다. 그들의 제품을 찾아 최대값을 반환하십시오.
이 솔루션은 구현하기 쉽지만 O(n 2 순서의 복잡성을 만드는 중첩 루프가 필요합니다. *n).
여기에서 구현해 보십시오.
효과적인 솔루션 배열에서 음수(nofNeg)와 0(nof0)의 수를 계산한 다음 이러한 조건에 따라 maxProd를 계산합니다.
사례 1 (nof0 =0이고 nofNeg는 짝수임) - 배열의 모든 요소를 곱으로 고려합니다.
maxProd =arr[0] * arr[1] * ... arr[n−1]
사례 2 (nof0 =0이고 nofNeg는 홀수임) - 배열의 가장 큰 음수 요소(0에 가장 가까움)를 제외한 배열의 모든 요소를 고려합니다.
사례 3 (nof0 !=0)- 곱에 대한 배열의 모든 0을 그대로 둡니다. 그리고 사례 1과 2와 유사한 사례를 살펴보세요.
특수 사례 - 0을 제외한 한 요소만 음수입니다. maxProd =0.
알고리즘
초기화 -
maxProd = 1;
1단계 -
Loop the array and count, nof0(number of zeros) and nofNeg(number of negatives), and find maxProd. maxProd = maxProd*arr[i], i −> 0 to n−1
2단계 -
consider the following cases − Case 1− if(nofNeg%2 == 0): maxProd Case 2− if(nofNeg%2 != 0): maxProd = maxProd/(largestNeg) Case 3 − if(nof0 == (n-1) and nofNeg == 1), maxProd = 0.
3단계
Print maxProd.
예시
우리 솔루션의 작동을 설명하는 프로그램
#include <iostream>
using namespace std;
int findMaxSubsetProd(int arr[], int n){
int larNeg = −1000;
int nofNeg = 0, Nof0 = 0;
int maxProd = 1;
for (int i = 0; i < n; i++) {
if (arr[i] == 0){
Nof0++;
continue;
}
else if (arr[i] < 0) {
nofNeg++;
if(larNeg < arr[i])
larNeg = arr[i];
}
maxProd = maxProd * arr[i];
}
if(nofNeg%2 == 0){
return maxProd;
}
else if(nofNeg%2 != 0)
return (maxProd / larNeg);
if(Nof0 == (n−1) and nofNeg == 1)
return 0;
return maxProd;
}
int main(){
int arr[] = {4, −2, 5, −1, 3, −6};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The maximum product subset of an array is "<<findMaxSubsetProd(arr, n);
return 0;
} 출력
The maximum product subset of an array is 720