이 문제에서 우리는 정수와 숫자 k의 배열 rr[]을 받습니다. 우리의 임무는 C++에서 크기 k의 부분열의 최대 곱을 찾는 프로그램을 만드는 것입니다.
문제 설명 − 여기에서 요소의 최대 곱을 갖는 크기 k, 1<=k <=n의 부분 수열을 찾아야 합니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력
arr[] = {1, 5, 6, -2, 0, 4} , k = 3 출력
120
설명
최대 곱을 갖는 크기 3의 부분 수열은 (5, 6, 4)입니다. 제품은 120입니다.
솔루션 접근 방식
이 문제를 해결하기 위해 먼저 배열 arr[]을 정렬한 다음, arr[] 요소와 k 값을 기반으로 정렬합니다. 방법은 다음과 같이 변경됩니다. -
사례 1(k가 짝수인 경우) − 곱은 0을 제외한 모든 최대 k 값을 가질 수 있습니다. 여기서 음수 값 쌍도 고려해야 합니다. 그들의 크기는 최대값의 결과를 줄 수도 있습니다.
사례 2(k가 홀수인 경우) − 이것은 약간 복잡한 조건이며 값은 결과 계산 방법을 정의합니다. 이 경우는 배열의 최대 요소를 기준으로 추가 분류해야 합니다.
사례 2.1(최대 개수가 양수인 경우) - 이것은 배열이 양수와 음수가 혼합되어 있음을 의미합니다. 이 경우 최대 k 요소를 찾고 부정적인 측면에서 최대 쌍도 검색합니다(가능한 경우 결과를 제공할 수 있음).
사례 2.2(최대 번호가 0인 경우) − 이것은 배열에 모든 음수 요소와 0이 포함되어 있음을 의미합니다. 이 경우 음수 요소의 홀수를 곱하면 음수가 생성되므로 최대 결과는 0이 됩니다. 즉, 0이 최대 곱입니다.
사례 2.3(최대 번호가 음수인 경우) − 이것은 배열에 음수만 포함되어 있음을 의미합니다. 이 경우 요소에 최소 크기를 곱하여 최대 결과를 얻을 수 있습니다. 즉, 최대 배열이 도움이 됩니다.
이런 식으로 k.최적의 결과를 얻으려면 요소 값과 k.값을 계속 확인해야 합니다. 이를 위해 우리는 결과에 음수 쌍을 곱하여 결과를 얻을 수 있는지 확인하기 위해 최대 및 최소 양쪽을 모두 배열로 유지합니다.
우리 솔루션의 작동을 설명하는 프로그램
예시
#include <bits/stdc++.h>
using namespace std;
int findMaxSubArrayProduct(int arr[], int n, int k) {
sort(arr, arr + n);
int maxProd = 1;
int i = 0, j = 0;
int maxprod, minprod;
if (arr[n - 1] == 0 && (k % 2 == 1))
return 0;
if (arr[n - 1] <= 0 && (k % 2 == 1)) {
for (i = n - 1; i >= n - k; i--)
maxProd *= arr[i];
return maxProd;
}
i = 0;
j = n - 1;
if (k % 2 == 1) {
maxProd *= arr[j];
j--;
k--;
}
k = k/2;
int it = 0;
while(it < k){
int minprod = arr[i] * arr[i + 1];
int maxprod = arr[j] * arr[j - 1];
if (minprod > maxprod) {
maxProd *= minprod;
i += 2;
} else {
maxProd *= maxprod;
j -= 2;
}
it++;
}
return maxProd;
}
int main() {
int arr[] = { 1, 5, 6, -2, 0, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout<<"The maximum product of subsequence of size "<<k<<" is "<<findMaxSubArrayProduct(arr, n, k);
return 0;
} 출력
The maximum product of subsequence of size 3 is 120