LeetCode 152 - Maximum Product Subarray

정수 배열 nums가 주어졌을 때, 원소들의 곱이 최대가 되는 연속된 부분 배열(Subarray)의 곱을 구하는 Medium 문제다. 음수끼리 곱하면 양수로 부호가 반전되는 성질을 고려하여, 매 위치마다 최댓값뿐 아니라 최솟값(가장 작은 음수)까지 함께 추적하며 O(n)에 해결했다.

문제 링크 & 설명

문제 링크: 152. Maximum Product Subarray
요약: 연속된 부분 배열 내 원소들을 모두 곱했을 때 얻을 수 있는 가장 큰 곱을 반환한다.

합을 구하는 문제(Kadane’s Algorithm)와 달리, 곱셈에서는 음수에 음수를 곱할 때 매우 큰 양수가 될 수 있다. 따라서 직전 단계까지의 최댓값뿐 아니라 최솟값(절댓값이 큰 음수)도 보관하고 있어야 현재 음수 값을 만났을 때 새로운 최댓값을 만들어낼 수 있다.

접근 방법

현재 위치까지의 최댓값 cur_max와 최솟값 cur_min을 관리한다.

res = nums[0]
cur_max = nums[0]
cur_min = nums[0]

for i in range(1, len(nums)):
    num = nums[i]

    if num < 0:
        tmp = cur_max
        cur_max = cur_min
        cur_min = tmp

    cur_max = max(num, cur_max * num)
    cur_min = min(num, cur_min * num)

    res = max(res, cur_max)

음수 반전 처리: 현재 원소 num이 음수라면 곱했을 때 최댓값과 최솟값의 부호가 바뀌므로, 계산 전에 cur_max와 cur_min을 스왑(Swap)한다.
상태 갱신:
- 새로운 cur_max는 현재 원소 자체(num)로 부분 배열을 새로 시작하는 경우와, 이전 최댓값에 현재 원소를 곱하는 경우(cur_max * num) 중 큰 값이다.
- 새로운 cur_min도 마찬가지로 num 자체와 이전 최솟값에 곱한 값 중 작은 값을 취한다.
결과 누적: 매 단계 갱신된 cur_max로 전체 최댓값 res를 갱신한다.

복잡도 분석

시간 복잡도: O(n)
- 배열의 원소를 한 번만 순회하며 상수 시간 연산으로 최댓값과 최솟값을 갱신한다.
공간 복잡도: O(1)
- 별도의 DP 배열 없이 세 개의 스칼라 변수(res, cur_max, cur_min)만 유지한다.

구현 코드

class Solution:

    def maxProduct(self, nums) -> int:
        if not nums:
            return 0

        res = nums[0]
        cur_max = nums[0]
        cur_min = nums[0]

        for i in range(1, len(nums)):
            num = nums[i]

            if num < 0:
                tmp = cur_max
                cur_max = cur_min
                cur_min = tmp

            cur_max = max(num, cur_max * num)
            cur_min = min(num, cur_min * num)

            res = max(res, cur_max)

        return res

요약 및 회고

부분 배열의 최대 곱 문제는 음수 곱셈의 반전 특성 때문에 단일 최댓값 추적만으로는 풀 수 없다. 음수를 만났을 때 cur_max와 cur_min의 역할을 맞바꿔주는 스왑 기법을 적용하면, 복잡한 분기 조건 없이도 깔끔하게 상태 전이를 일원화할 수 있다.