Maximum Product Subarray

정수 배열이 주어졌을 때, 공집합이 아닌 부분 배열의 곱이 최대가 되는 부분 배열을 찾고 그 곱을 구하자.

모든 곱은 32비트 정수로 표현되는 것이 보장된다.

부분 배열이란 배열에서 연속되는 부분 시퀀스를 뜻한다.

배열의 길이는 최대 \(2 \times 10^4\) 이고 각 값은 -10~10이다.

O(N^2) - 타임아웃

부분 배열의 최대 합랑 비슷한 문제다. 역시 비슷하게 Brute Force를 생각해볼 수 있는데, 역시나 타임아웃이 난다.

def maxProduct(nums):
    maxp = float('-inf')
    for i in range(len(nums)):
        curp = 1
        for j in range(i, len(nums)):
            curp *= nums[j]
            maxp = max(maxp, curp)
    return maxp

• 합과는 다르게 곱의 초기값은 1이 되어야 정상적으로 누적되는 것만 주의하면 된다.

O(N) - Two Pass

대관절 어떻게 하면 좋을까?? 이 문제를 처음 봤을 때에는 Brute Force 말고는 다른 방법이 도저히 떠오르질 않더라. 그래서 여러가지 힌트를 살펴보았고 접근 방법을 정리해보려고 한다.

일단 부분합과는 다른 부분곱만의 특이한 점을 관찰하면 다음과 같다:

• 기존 방법처럼 인덱스 i 이전까지의 부분 배열로 곱을 만들려고 하면 0이 발을 붙잡고 넘어진다. 원소가 0이면 이때까지 쌓아온 모든 값이 초기화되기 때문이다. 곱에서 초기화란 곧 1로 초기화되는 것과 같다. 즉, 일종의 구분자로 생각해도 된다.
• 음수의 경우도 특이하다. 음수를 홀수번 곱하면 음수이고, 짝수번 곱하면 양수가 된다. 따라서, 합과는 다르게, 부분 배열에 음수가 몇 개 있는지가 최대 곱에 영향을 미친다.

좀더 구체적인 예제를 가지고 생각을 해보자.

[2, 3, -4, 5]

음수가 하나인 경우를 생각해보자. 왼쪽에서부터 누적 곱을 구해 나가면 [2, 6, -24, -120]가 되고, 오른쪽에서부터 가면 [5, -20, -60, -120]가 된다. 즉, 음수 -3이 배열을 반으로 나눠버린다는 것을 알 수 있다. 따라서 이 중 최대값은 왼쪽에서부터 음수 직전까지를 곱한 6이 된다.

[2, -3, -4, 5]

이번에는 음수가 두개인 경우를 생각해보자. 앞에서 음수를 두 번 곱하면 양수가 된다고 했는데, 이게 어떤 영향을 미치는지 눈으로 확인할 수 있다. 마찬가지로 앞에서부터 곱을 누적하면 [2, -6, 24, 120]이 되고, 뒤에서부터 곱을 누적하면 [5, -20, 60, 120]이 되어 앞에서 곱하나 뒤에서 곱하나 최대 값은 120이 된다.

결국 중요한 케이스는 음수가 세 개 이상이면서 홀수인 경우다. 그리고 그 경우에는 앞에서 곱을 누적한 것과 뒤에서 곱을 누적한 것 중에 최대값이 있다.

이 성질을 이용해서 다음과 같이 구현할 수 있다.

def maxProduct(nums):
    maxp = float('-inf')
    curp = 1
    for n in nums:
        curp *= n
        maxp = max(maxp, curp)
        if n == 0:
            curp = 1

    curp = 1
    for n in reversed(nums):
        curp *= n
        maxp = max(maxp, curp)
        if n == 0:
            curp = 1
    return maxp

• 먼저 정방향으로 훑으면서 누적 곱을 계산해서 최대 값을 갱신한다. 이때, 지금 값이 0이라면, 이후의 곱을 위해서 누적 곱을 1로 초기화한다. 이를 통해 누적 곱 curp의 값이 인덱스 i까지의 부분 배열 중에서 값이 0이 아닌 가장 나중의 위치부터 i까지의 누적 곱이 담기도록 보장할 수 있다.
• 그 후 역방향으로 훑으면서 똑같이 최대 값을 갱신한다. 이렇게 두 번 훑으면 최대 값에는 누적 곱의 최대 값이 담긴다.