152. Maximum Product Subarray

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

문제 설명

정수 배열 nums가 주어질 때, 가장 큰 곱 값을 갖는 연속적인 하위 배열을 return 하는 문제이다. 이때, 하위 배열의 요소들은 연속되어야 한다. 예를 들어 num = [1,2,3] 일 때, 연속되지 않는 [1,3]은 하위 배열이 될 수 없다.
Example 1)
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3]이 최대곱을 가지는 하위 배열이다.
Example 2)
Input: nums = [-2,0,-1]
Output: 0

만약 주어진 배열이 양수라면 ex.1,2,3
.
12에서 23으로 증가시켜나갈수록 더 값이 커진다

그런데 음수가 있는 경우 Ex. -1,-2,-3
곱하면 더 그 수가 작아진다.

그래서
max_prod, min_prod를 만든 뒤
음수와 양수를 구분해서
음수 음수 = 양수
양수 음수 = 음수
등을 구별하는 것이 관건이다.

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        max_prod, min_prod, ans = nums[0], nums[0], nums[0]
        for i in range(1, len(nums)):
            tmp = max_prod
            max_prod = max(max_prod * nums[i], min_prod * nums[i], nums[i])
            min_prod = min(tmp * nums[i], min_prod * nums[i], nums[i])
            ans = max(ans, max_prod)
        return ans

22.11.14 복습