152. Maximum Product Subarray

1. Description

• 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.

2. Example

Example 1

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

Example 2

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

3. Solution

• Runtime: 12ms
• 설명
  • 이 코드에서는 최댓값과 최솟값을 같이 구해야한다.
    • 이유는
      • nums리스트에는 음수값도 같이 포함되어 있다.
      • 만약 음수값과 음수값이 곱하게 된다면 양수 값이 나와 값이 커질 가능성도 있기 때문에 cur_min을 만들어 같이 비교해야 한다.
    • temp를 cur_max * n값을 저장하여 cur_max값이 바뀌어도 비교할 수 있게 한다.

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        res = max(nums)
        cur_max = cur_min = 1
 
        for n in nums:
            temp = cur_max * n
 
            cur_max = max(temp, cur_min * n, n)
            cur_min = min(temp, cur_min * n, n)
 
            res = max(res, cur_max)
        
        return res

4. What I Learned

References

• Youtube