C++에서 두 번의 순회로 최대 곱 부분 배열 구하기

이 문제에서는 정수로 이루어진 배열 arr[]가 주어지며, C++를 사용해 두 번의 순회(Two Traversals) 방식으로 최대 곱 부분 배열(Maximum Product Subarray)을 찾는 프로그램을 작성하는 것이 목표입니다.

문제 설명

주어진 배열에서 인덱스 0부터 시작하는 순회(왼쪽 → 오른쪽)와 인덱스 n-1부터 시작하는 순회(오른쪽 → 왼쪽), 총 두 번의 순회를 이용해 곱이 가장 큰 부분 배열의 값을 구합니다.

예제로 문제 이해하기

입력

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

출력

240

설명

부분 배열 = {4, -2, 5, -6}
최대 곱 = 4 * (-2) * 5 * (-6) = 240

음수가 두 개 포함되어 있어 서로 곱해지면 양수가 되고, 여기에 0은 곱셈에 영향을 주지 않도록 처리하면 위와 같이 최댓값 240을 얻을 수 있습니다.

해결 접근 방법

두 번의 순회를 활용하는 방식은 다음과 같습니다.

1. 왼쪽 → 오른쪽 순회: 인덱스 0부터 n-1까지 배열을 순회하며 각 요소를 누적 곱에 곱해 나갑니다.

2. 오른쪽 → 왼쪽 순회: 인덱스 n-1부터 0까지 반대 방향으로 순회하며 같은 방식으로 누적 곱을 계산합니다.

순회 중 누적 곱이 0이 되면, 이후 곱셈 결과가 모두 0으로 고정되는 것을 막기 위해 값을 1로 초기화합니다. 마지막으로 두 방향에서 얻은 최댓값 중 더 큰 값을 정답으로 반환합니다.

C++ 구현 코드

#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

시간 복잡도

배열을 앞뒤로 각각 한 번씩 순회하므로 시간 복잡도는 O(n)이며, 추가적인 저장 공간 없이 몇 개의 변수만 사용하므로 공간 복잡도는 O(1)입니다.