[LeetCode] 152. Maximum Product Subarray - 파이썬(Python)

문제 링크 : https://leetcode.com/problems/maximum-product-subarray/

Maximum Product Subarray - LeetCode

유형 : 동적 계획법(Dynamic Programming)

문제 설명

정수 배열 nums가 주어질 때, 가장 큰 곱 값을 갖는 연속적인 하위 배열을 return 하는 문제이다. 이때, 하위 배열의 요소들은 연속되어야 한다. 예를 들어 num = [1,2,3] 일 때, 연속되지 않는 [1,3]은 하위 배열이 될 수 없다.

Example 1)
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3]이 최대곱을 가지는 하위 배열이다.

Example 2)
Input: nums = [-2,0,-1]
Output: 0

제한사항

• 1 <= nums.length <= 2 * 10^4
• -10 <= nums[i] <= 10

문제 풀이

성공 코드

from typing import List

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        
        min_dp = [nums[0]]
        max_dp = [nums[0]]
        
        for idx in range(1,len(nums)):
            prev_idx = idx - 1
            
            num = nums[idx]
            cand0 = num
            cand1 = max_dp[prev_idx] * num
            cand2 = min_dp[prev_idx] * num
            
            max_val = max(cand0,cand1,cand2)
            min_val = min(cand0,cand1,cand2)
            
            max_dp.append(max_val)
            min_dp.append(min_val)
            
        max_product = max(max_dp)
        return max_product

시간 복잡도 : O(n)

n은 nums의 크기이다.

공간 복잡도 : O(n)

n은 nums의 크기이다.