[Leet Code] 152. Maximum Product Subarray

문제 링크

문제 설명

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

It is guaranteed that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.

예제 1

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

제한

1 <= nums.length <= 2 * 10^4
-10 <= nums[i] <= 10
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

풀이

i번째의 최대 부분배열의 곱을 구하기 위해서는 부호를 신경써야 한다.

부호에 따라 최솟값이 최댓값이 될 수 있기 때문에,
i-1번째의 최소 부분배열의 곱과 최대 부분배열의 곱 모두 구해놓고 비교해야 한다.

이때 i-1번째의 최소 부분배열의 곱이 음수 + i번째 원소가 음수 -> 최댓값이 될 것이고,
i-1번째의 최소 부분배열의 곱이 양수 + i번째 원소가 양수 -> 최댓값이 될 것이다.

나는 처음에 최대, 최소 부분 배열의 곱을 저장할 배열 변수를 만들어서, 비교하고 최대 부분배열의 곱을 구했다.

시간복잡도는 O(N+N) -> O(N)정도가 될 것 같다.
리턴할 때 배열에서 MAX값을 찾는데, 내장함수 max()는 O(N)의 시간복잡도를 갖는다.
반복문과 max() 두가지에서 O(N+N) -> O(N) 정도로 생각했다.

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        minProduct = [nums[0]]
        maxProduct = [nums[0]]
        for i in range(1, len(nums)):
            x = min(nums[i], nums[i]*minProduct[-1],nums[i]*maxProduct[-1])
            y = max(nums[i], nums[i]*minProduct[-1],nums[i]*maxProduct[-1])
            minProduct.append(x)
            maxProduct.append(y)
        return max(maxProduct)
        

배열 변수를 쓰지 않고, 조금 더 빠르고 깔끔한 코드로 개선이 가능하다.

최대 최소 값을 저장하는 변수 2개로 최적화가 가능하고, 이 경우 시간복잡도는 O(N)이 될 것이다.
(max()는 두가지 값 중에서 최댓값을 비교하게 되므로 아주 미미할 것) 어쨌든 조금 빠르긴 하다.

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        minProduct = nums[0]
        maxProduct = nums[0]
        answer = nums[0]
        for i in range(1, len(nums)):
            x = max(nums[i], nums[i]*minProduct, nums[i]*maxProduct)
            y = min(nums[i], nums[i]*minProduct, nums[i]*maxProduct)
            maxProduct = x
            minProduct = y
            answer = max(maxProduct, answer)
        return answer