문제

• 정수 리스트 nums
• 제일 큰 곱을 가지는 subarray 찾기
• 곱 return

풀이

• 전에 제일 큰 합을 가지는 걸로 풀었던 것 같은데
• dp
• 음수 * 음수 = 양수 가 됨을 고려
• dp[i][0]은 그냥 현재에 가장 큰 곱
• dp[i][1]은 현재에 절댓값이 가장 큰 곱
• O(n)으로 풀어보려 노력했으나... 0이란 벽에 부딪혀 실패

O(n**2)

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        N = len(nums)
        tmp = 1
        maxi = tmp
        
        for i in range(N):
            tmp = nums[i]
            maxi = max(maxi, tmp)
            for j in range(i+1, N):
                tmp *= nums[j]
                maxi = max(maxi, tmp)
        return maxi
               

아 타임리밋,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

다시 O(n)으로 생각하자

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        product = set()
        product.add(1)
        maxi = nums[0]
        
        for n in nums:
            newProduct = set()
            newProduct.add(n)
            maxi = max(maxi, n)
            for p in product:
                newProduct.add(n*p)
                maxi = max(maxi, n*p)
            product = newProduct
        
        return maxi

• O(n)까지는 아닐듯

속도도 많이 느리다

풀이 참고

• 결국은 각 상태에서 min과 max만 알면 돼
• min이 절댓값이 가장 큰 음수라면, 다음 음수를 만났을 때 max가 되고
• min이 그냥 작은 양수라면, max가 제일 커서 영향 주지 않음
• 처음에 했던 발상이였는데 (2 변수로 dp 하는거)
• 단순히 min, max일거라고 생각치 못했다
• abs계산을 하고 어쩌구 했는데~~

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        N = len(nums)
        minProduct = nums[0]
        maxProduct = nums[0]
        maxi = maxProduct
        
        for i in range(1, N):
            product = set()
            product.add(minProduct*nums[i])
            product.add(maxProduct*nums[i])
            product.add(nums[i])
            
            minProduct = min(product)
            maxProduct = max(product)
            
            maxi = max(maxi, maxProduct)
        
        return maxi

그렇게 엄청 빠르진 않네