LeetCode : Maximum Product Subarray (Medium)

0. Overview


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까지 최대/최소 누적 곱을 유지하는 리스트를 생성하여, 비교를 통해 최대 누적곱 값을 구할 수 있습니다.

좋은 웹페이지 즐겨찾기