C++ 최대 곱 부분 배열(Maximum Product Subarray) 구현하기 | 음수 처리 케이스 포함

이 문제에서는 양수와 음수를 모두 포함하는 정수 배열이 주어지며, C++로 최대 곱 부분 배열(Maximum Product Subarray)을 계산하는 프로그램을 작성하는 것이 목표입니다.

문제 설명

배열에는 양수, 음수, 그리고 0이 섞여 있을 수 있습니다. 우리는 배열의 연속된 요소들로 만들 수 있는 부분 배열(subarray)의 곱을 계산하고, 그중 곱이 가장 커지는 부분 배열을 찾아야 합니다.

예시로 이해하기

입력

arr[] = {-1, 2, -7, -5, 12, 6}

출력

5040

설명

최대 곱을 갖는 부분 배열은 {2, -7, -5, 12, 6}이며, 그 곱은 다음과 같습니다.

곱 = 5040

해결 접근 방법

이 문제를 해결하려면 배열을 순회하면서 두 가지 값을 관리해야 합니다.

• maxVal: 현재 요소까지의 최대 곱
• minVal: 현재 요소까지의 최소 곱(음수 극값)

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

마무리

이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 음수로 인해 최댓값과 최솟값이 뒤바뀌는 상황과 0으로 인해 부분 배열이 끊기는 상황을 모두 고려하는 것이 핵심 포인트입니다.