Maximum Product Subarray

LeetCode의 Maximum Product Subarray 문제를 함께 풀어보도록 하겠습니다.

문제

정수로 이뤄진 배열이 주어졌을 때, 정수들의 최대 곱을 만들어내는 연속되는 부분 배열을 찾아서 반환하라.

예제

Input: nums = [2, 3, -2, 4]
Output: 6

입력 배열에서 부분 배열 [2, 3] 내의 정수를 모두 곱하면 6으로 가장 크다.

풀이 1

이 문제를 푸는 가장 단순한 방법은 주어진 배열로 부터 만들 수 있는 모든 부분 배열을 만든 후 그 안의 정수를 모두 곱해보는 것입니다. 주어진 배열의 각 인덱스를 부분 배열의 시작 지점으로 잡고, 종료 지점을 한칸씩 늘려가면 모든 경우의 부분 배열을 만들 수 있을 것입니다. 담고 있는 정수들의 곱이 가장 큰 배열을 반환해야하므로, 각 부분 배열에서 구한 곱을 여태까지 구한 최대 곱과 반복해서 비교를 하면 됩니다.

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        max_product = nums[0]
        for start in range(len(nums)):
            for end in range(start, len(nums)):
                product = 1
                for i in range(start, end + 1):
                    product *= nums[i]
                max_product = max(product, max_product)
        return max_product

이 풀이는 삼중 루프를 사용하고 있기 때문에 시간 복잡도가 O(n^3)인 매우 비효율적인 알고리즘입니다. 고정된 개수의 변수 외에는 추가 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다.

풀이 2

위 풀이를 살펴보면 정수들의 곱을 구할 때 내부 for 문 안에서 중복 연산이 상당히 많이 발생하는 것을 볼 수 있습니다. 사실 부분 배열의 종료 지점이 늘어날 때 마다 매번 시작 지점부터 종료 지점까지의 정수를 다 곱할 필요는 없습니다. 종료 지점이 한 칸씩 늘어나므로 이전 종료 지점까지 누적된 곱에 이번 종료 지점에 추가되는 새로운 정수만 곱해주면 되겠습니다.

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        max_product = nums[0]
        for start in range(len(nums)):
            product = 1
            for end in range(start, len(nums)):
                product *= nums[end]
                max_product = max(product, max_product)
        return max_product

내부에 있는 루프를 하나가 사라졌기 때문에 이 풀이의 시간 복잡도는 O(n^2)로 개선이 되었습니다. 반면에 공간 복잡도는 변함없이 O(1)입니다.

풀이 3

여기서 만족할 수도 있지만 O(n^2)은 여전히 다소 아쉬운 시간 복잡도일 것입니다. 이 것보다 더 나은 알고리즘은 없을까요? 🤔

다양한 형태의 배열이 주어졌을 때, 어떻게 최대 곱이 구해질 수 있는지 한 번 천천히 생각을 해보겠습니다.

먼저 모두 양수로 이뤄진 배열이 주어지면 최대 곱은 어떻게 구할 수 있을까요? 맞습니다! 모조리 곱해버리면 최대 곱을 얻을 수 있을 것입니다.

[2, 3, 4]
최대곱 = 2 * 3 * 4

그럼 모두 음수로 이뤄진 배열이 주어지면 최대 곱은 어떻게 구할 수 있을까요? 살짝 골치가 아파지는데요… 음수를 2번 곱하면 양수가 되지만 여기서 또 음수를 곱하면 음수가 되기 때문입니다.

[-2, -3, -4]
최대곱 = -3 * -4 = 12

이 번에는 배열이 0을 포함하고 있으면 어떨까요? 아무리 큰 수라도 0이랑 곱하면 0이 되기 때문에 0을 포함한 부분 배열의 최대 곱은 0이 되어 버립니다.

[2, 3, 0, 4]
최대곱 = 2 * 3 = 6

이 3가지 경우의 수를 잘 생각해보면 현재 위치에서 만들 수 있는 최대 곱을 이전 위치에서 만들 수 있는 최대 곱이나 최소 곱으로 부터 도출해낼 수 있습니다.

  1. 이전 위치의 최대곱 x 현재 위치에 있는 정수
  2. 이전 위치의 최소곱 x 현재 위치에 있는 정수
  3. 현재 위치에 있는 정수

이 알고리즘이 제대로 동작하는지 주어진 예제에서 적용을 해볼까요?

  • 인덱스 0:
[2, 3, -2, 4]
 ^
최소 곱 = 2
최대 곱 = 2 (최대 곱 갱신)
  • 인덱스 1:
[2, 3, -2, 4]
    ^
최소 곱 = 3
최대 곱 = 2 * 3 = 6 (최대 곱 갱신)
  • 인덱스 2:
[2, 3, -2, 4]
        ^
최소 곱 = 6 * -2 = -12
최대 곱 = -2
  • 인덱스 3:
[2, 3, -2, 4]
           ^
최소 곱 = -12 * 4 = -48
최대 곱 = 4

이 과정을 그대로 코드로 구현해볼까요?

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        res = nums[0]
        min_product = max_product = 1
        for num in nums:
            min_product, max_product = min(num, min_product * num, max_product * num), max(num, min_product * num, max_product * num)
            res = max(res, max_product)
        return res

이번 풀이에서는 루프를 하나만 사용함으로써 시간 복잡도를 O(n)로 대폭 향상시킬 수 있었습니다. 🎉

참고로 이렇게 이전 위치에서 구한 연산 결과를 현재 단계에서 재활용하는 기법을 다이나믹 프로그래밍이라고 합니다.

마치면서

이 문제는 기존에 다루었던 Maximum Subarray와 풀이 방법이 상당히 유사하나 좀 더 어려우니 참고바라겠습니다.