152. Maximum Product Subarray

[zeikar]

Problem link

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

Problem Summary

배열에서 subarray 곱 중 가장 최댓값을 구하는 문제

Solution

곱할 때 핵심은 현재까지 최댓값에 -를 곱하게 되면 최소가 되고 -를 더 곱하게 되면 다시 최대가 된다는 점이다.
즉 최대 최소가 번갈아가며 나올 수 있다는 것이다. 여기에서 maxim, minim 으로 최대, 최소를 다 선언해두고 계속 갱신해주면 된다.

Source Code

from typing import List


class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        ans = nums[0]
        maxim = nums[0]
        minim = nums[0]

        for i in range(1, len(nums)):
            if nums[i] < 0:
                maxim, minim = minim, maxim
            maxim = max(maxim * nums[i], nums[i])
            minim = min(minim * nums[i], nums[i])
            ans = max(ans, maxim)

        return ans