최대 제품 하위 배열 | C++에 부정적인 제품 사례 추가

이 문제에서는 정수 배열(양수 및 음수)이 제공됩니다. 우리의 임무는 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