[Leetcode] 152. Maximum Product Subarray

문제 바로가기

Time Complexity: $O(n)$
Space Complexity: $O(1)$

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        """
        0이 아닌 정수가 주어졌을 때, 연속되는 곱의 최대값은 모든 수의 곱과 처음 등장하는 음수 다음
        수부터 곱한 수 중 양수인 수를 고르면 된다.
        음수의 수가 홀수이면 첫 음수 이후부터의 누적 곱, 짝수이면 모든수의 곱이 정답이 된다.
        0이 존재한다면 0 이전까지의 최대 값과 0 이후의 최대 값을 비교하면 된다. 0을 곱하면 0이므로
        연속된 곱이 의미가 없기 때문이다.
        """
        maxSoFar = float("-inf")
        posProdSoFar = negProdSoFar = None
        
        for num in nums:
            if num == 0:
                maxSoFar = max(maxSoFar, posProdSoFar or num)
                posProdSoFar = negProdSoFar = None
            elif num < 0:
                maxSoFar = max(maxSoFar, posProdSoFar or num)
                posProdSoFar, negProdSoFar = negProdSoFar, posProdSoFar
                negProdSoFar = negProdSoFar * num if negProdSoFar else num
                if posProdSoFar: posProdSoFar *= num
            else:
                posProdSoFar = posProdSoFar * num if posProdSoFar else num
                if negProdSoFar: negProdSoFar *= num
        
        if posProdSoFar:
            maxSoFar = max(maxSoFar, posProdSoFar)
        return maxSoFar