최대 곱 하위 배열 - C++에서 두 개의 순회 사용

이 문제에서는 정수 배열 arr[]이 제공됩니다. 우리의 임무는 최대 곱 하위 배열을 찾는 프로그램을 만드는 것입니다 - 두 개의 Traversalsin C++를 사용합니다.

문제 설명 − 여기 배열에서 인덱스 0과 다른 인덱스(n-1)의 두 순회를 사용하여 최대 곱 하위 배열을 찾습니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

arr[] = {4, -2, 5, -6, 0, 8}

출력

240

예

Subarray = {4, -2, 5, -6}
Maximum product = 4 * (-2) * 5 * (-6) = 240

해결 방법

두 개의 순회를 사용하여 이 문제를 해결합니다. 여기에서 왼쪽에서 오른쪽으로, 즉 인덱스 0에서 n-1로 순회하기 위해 두 개의 로컬 최대값을 사용하여 maximumproduct를 찾을 것입니다. 그리고 하나는 오른쪽에서 왼쪽으로, 즉 indexn-1에서 0으로 순회하는 것입니다. 나머지 알고리즘은 최대 곱 하위 배열을 찾는 것과 동일합니다.

우리 솔루션의 작동을 설명하는 프로그램

예

#include<iostream>
using namespace std;
int CalcMaxProductSubArray(int arr[], int n) {
   int frntMax = 1, rearMax = 1, maxVal = 1;
   for (int i=0; i<n; i++) {
      frntMax = frntMax*arr[i];
      if (frntMax == 0)
         frntMax = 1;
   }
   for (int i=n-1; i>=0; i--) {
      rearMax = rearMax * arr[i];
      if (rearMax == 0)
         rearMax = 1;
   }
   maxVal = max(frntMax, rearMax);
   return maxVal;
}
int main() {
   int arr[] = {4, -2, 5, -6, 0, 8};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"Maximum product subarray is "<<CalcMaxProductSubArray(arr, n);
   return 0;
}

출력

Maximum product subarray is 240