이 문제에서는 정수 배열(양수 및 음수)이 제공됩니다. 우리의 임무는 C++에서 최대 ProductSubarray를 계산하는 프로그램을 만드는 것입니다.
문제 해결 − 여기에 양수, 음수, 0을 포함하는 배열이 있습니다. 배열의 요소에 의해 생성된 하위 배열의 곱을 찾아야 합니다. 그리고 하위 배열의 곱을 최대화합니다.
문제를 이해하기 위해 예를 들어 보겠습니다.
입력
arr[] = {-1, 2, -7, -5, 12, 6}
출력
5040
설명
최대 곱이 있는 하위 배열은 {2, -7, -5, 12, 6}입니다.
Product = 5040
솔루션 접근 방식
이 문제를 해결하기 위해 배열과 하위 배열의 최대 곱이 주어지고 현재 요소까지의 최대 곱인 maxVal과 곱의 음의 최대값인 minVal을 관리합니다. 그런 다음 현재 값을 기반으로 maxVal 및 minVal이 -
로 업데이트됩니다.사례 1 - 요소가 긍정적임 − 배열을 곱하여 maxVal 및 minVal을 업데이트합니다.
사례 2 - 요소가 0임 − 0을 곱하면 0이 되기 때문에 현재 하위 배열을 나눕니다.
사례 3 - 요소가 음수임 − 두 값을 모두 음수 값으로 업데이트하여 최대값을 만듭니다.
우리 솔루션의 작동을 설명하는 프로그램
예시
#include <iostream> using namespace std; int min(int a, int b){ if(a < b) return a; return b; } int max(int a, int b){ if(a > b) return a; return b; } int CalcMaxProductSubArray(int arr[], int n) { int i = 0; int maxVal = -1000; int localMax = 1; int localMin = 1; int lastMax; while(i < n) { int currentVal = arr[i]; if (currentVal > 0) { localMax = (localMax * currentVal); localMin = min(1, localMin * currentVal); } else if (currentVal < 0) { lastMax = localMax; localMax = (localMin * currentVal); localMin = (lastMax * currentVal); } else { localMin = 1; localMax = 0; } maxVal = max(maxVal, localMax); if (localMax <= 0) localMax = 1; i++; } return maxVal; } int main(){ int arr[] = { -1, 2, -7, -5, 12, 6 }; int n = 6; cout<<"The maximum product Subarray is "<<CalcMaxProductSubArray(arr, n); return 0; }
출력
The maximum product Subarray is 5040