Leetcode: Maximum product subarray

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

element의 곱이 최대가 되는 subarray를 찾는 문제이다. subarray 문제는 i번째 원소에 대해서 살펴볼 때에, 지금까지의 maximum product subarray의 값에 현재의 값을 처리한 값과 현재의 값 nums[i]에 대하여 비교해서 해결하는 식으로 푸는 경우가 많다.(비슷하지만 조금 더 간단한 문제로는 https://leetcode.com/problems/maximum-subarray/ 가 있다.) 이 문제도 마찬가지로 해결할 수 있는데, 한 가지 조심해야 하는 점은 이 문제가 곱을 다루고 있다는 것이다. 곱셈의 경우, 부호에 따라 최솟값이던 값이 최댓값이 될 수도 있기 때문에, i번째까지의 maximum product subarray를 다룰 때에 i-1번째까지의 maximum product 값과 minimum product값이 둘 다 필요하다.

예를 들어, i-1까지의 maximum이 12였고 minimum이 -24인 경우, nums[i]가 -2이면 i-1까지의 minimum을 이용하는 것이 더 큰 값이 나온다. 

from typing import List


class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        answer = nums[0]
        prev_min = nums[0]
        prev_max = nums[0]

        for i in range(1, len(nums)):
            num = nums[i]
            prev_min, prev_max = min(num, min(prev_min * num, prev_max * num)), max(num, max(prev_min * num, prev_max * num))
            answer = max(answer, max(prev_min, prev_max))
        return answer

prev_min과 prev_max를 유지하고, prev_min은 기존의 prev_min, prev_max에 nums[i]를 곱한 값 중 적은 것으로, prev_max는 기존의 prev_min, prev_max에 nums[i]를 곱한 값 중 큰 값으로 치환한다. (python은 variable swap이 가능하기에 이런 식으로 구현이 가능하지만, 다른 언어들의 경우 따로 tmp variable을 두고 swap을 해줘야 한다.)

 

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