LeetCode : Maximum Product Subarray (Medium)

0. Overview

• 풀이 날짜 : 2021-06-18
• 풀이 소요 시간 : 30m
• LeetCode URL : https://leetcode.com/problems/maximum-product-subarray/

1. Problem

2. Solution

from typing import List

def maxProduct(nums: List[int]) -> int:
    min_candidates = [n for n in nums]
    max_candidates = [n for n in nums]
    
    for i in range(1, len(nums)) :
        max_candidates[i] = max(min_candidates[i-1] * nums[i], max_candidates[i-1] * nums[i], max_candidates[i])
        min_candidates[i] = min(min_candidates[i-1] * nums[i], max_candidates[i-1] * nums[i], min_candidates[i])
        #print(max_candidates, min_candidates)
    return max(max_candidates)

3. Review

• 앞서 풀이한 'Maximum Subarray' 문제와 동일하게 Dynamic Programming 방식을 활용하여 문제를 해결할 수 있습니다.
• 누적합을 구하는 문제와 달리, 음수 여부에 따라 누적 곱이 달라질 수 있으므로, i번째 Subarray까지 최대/최소 누적 곱을 유지하는 리스트를 생성하여, 비교를 통해 최대 누적곱 값을 구할 수 있습니다.