Leetcode 152. Maximum Product Subarray

문제

Given an integer array nums, find a 
subarray
 that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

• 정수가 담긴 큰 배열이 하나가 주어질때, 서브어레이들 중 값들의 곱이 가장 최대가 되는
  결과 값을 구하여라
  서브어레이 : 배열 내에서 연속되는 숫자들 Ex. [1, 2, 3] -> [2, 3] 은 서브어레이, [1, 3]은 이어지지 않아
  아님

예시

[2, 3, -2, 4]

[2, 3] 이 곱이 6으로 가장 큰 곱을 가진 서브어레이이다.

제한

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

풀이

• 음수를 곱하면 값이 최소가 될수도 있고 최대가 될수도 있다.
• 음수를 곱했을때 최소가 되면 다음 음수를 곱했을때 최대가 될수 있다.

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        M = nums[0]
        m = nums[0]
        p = nums[0]

        for num in nums[1:]:
            if num < 0:
                M, m = m, M

            M = max(num, M * num)
            m = min(num, m * num)
            p = max(p, M)

        return p