파이썬으로 풀어보는 최대 곱 부분 배열(Maximum Product Subarray) 문제

문제 개요

정수 배열 nums가 주어졌을 때, 최소 하나의 숫자를 포함하는 연속된 부분 배열(contiguous subarray) 중에서 원소들의 곱이 가장 큰 값을 찾는 것이 이번 문제의 목표입니다.

예를 들어 배열이 [2, 3, -2, 4]라면, 연속된 부분 배열 [2, 3]의 곱인 6이 최댓값이므로 출력 결과는 6이 됩니다.

해결 접근 방법

이 문제는 동적 계획법(DP)으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 음수의 존재 때문에 각 위치에서 최대 곱과 최소 곱을 동시에 추적해야 한다는 점입니다. 음수끼리 곱하면 양수가 되므로, 지금까지의 최솟값이 새로운 최댓값으로 뒤집힐 수 있기 때문입니다.

알고리즘의 단계는 다음과 같습니다.

• 배열 nums와 같은 크기의 max_list와 min_list를 생성하고 0으로 채웁니다.
• max_list[0] = nums[0], min_list[0] = nums[0]으로 초기화합니다.
• i를 1부터 배열 길이까지 반복하며 다음을 수행합니다.
  • max_list[i] = max(max_list[i-1]*nums[i], min_list[i-1]*nums[i], nums[i])
  • min_list[i] = min(min_list[i-1]*nums[i], nums[i], max_list[i-1]*nums[i])
• 모든 반복이 끝나면 max_list의 최댓값을 반환합니다.

구현 예제

class Solution(object):
    def maxProduct(self, nums):
        max_list = [0] * len(nums)
        min_list = [0] * len(nums)
        max_list[0] = nums[0]
        min_list[0] = nums[0]
        for i in range(1, len(nums)):
            max_list[i] = max(max(max_list[i-1]*nums[i], min_list[i-1]*nums[i]), nums[i])
            min_list[i] = min(min(min_list[i-1]*nums[i], nums[i]), max_list[i-1]*nums[i])
        return max(max_list)

ob1 = Solution()
print(ob1.maxProduct([2, 3, -2, 4, -5, -6, 2]))

입력

[2, 3, -2, 4, -5, -6, 2]

출력

240

동작 원리 살펴보기

위 입력 배열의 경우, 부분 배열 [2, 3, -2, 4, -5]의 곱이 2 × 3 × (-2) × 4 × (-5) = 240으로 최댓값이 됩니다. 여기서 음수 -2와 -5가 만나 서로 상쇄되어 양수가 되면서 곱이 크게 증가했습니다.

이처럼 음수가 포함된 배열에서는 현재 위치까지의 최댓값만 보는 것으로는 정답을 구할 수 없습니다. 절댓값이 큰 음수(즉, 최솟값) 역시 함께 저장해 두어야, 이후 또 다른 음수를 만났을 때 최댓값으로 전환되는 경우를 놓치지 않을 수 있습니다. 이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)으로 배열을 한 번만 순회하면 되기 때문에 매우 효율적입니다.