[4코3파] #288. Leetcode 152. Maximum Product Subarray

[4코3파] 1명의 스위프트 개발자가 도망가고 4명의 코틀린 개발자, 3명의 파이썬 개발자의 코딩 테스트 스터디 : 4코3파

START :

[3코1파] 2023.01.04~ (288일차)
[4코1파] 2023.01.13~ (280일차)
[4코3파] 2023.10.01 ~ (18일차)

Today :

2023.10.17 [287일차]

152. Maximum Product Subarray

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

문제 설명

정수가 담긴 배열 nums가 주어질 때, subarray 배열의 연속된 부분 배열의 곱 중에서 가장 큰 값을 returnv 함

문제 풀이 방법

해당 문제는 brute force로 풀게되면 시간복잡도 O(n^2) 으로 풀 수 있는데,
패턴을 찾아서 dp로 풀게되면 O(n)으로 풀 수 있다.
먼저, 모든 배열이 양수로 되어 있다면 모든 배열의 곱이 가장 큰 수이다.
모든 배열이 음수로 되어 있다면, n-1배열 까지의 곱과 n번째의 배열을 곱하면 가장 큰 수이다.
그러나, edge case 로 중간에 0이 껴있을 경우나, 음수와 양수가 골고루 분포 되어 있는 배열일 경우는 위의 패턴이 깨지게 된다.

subarray의 곱셈 중 가장 큰 수를 파악하기 위해서는
처음부터 끝까지 배열을 탐색할 때 해당 인덱스 기준으로 계산되는 min값과 max값을 계산해 나가면서 현재까지의 min, max값을 update 해주어야 한다.
위에서 말한 edge case인 0을 만나면 기존의 계산은 사라지므로, 0 일경우에는 1로 reset 한후 min, max를 계산해나가고 마지막 max값을 return 한다.

이 때 마지막 max값은 처음 계산시 주어진 배열에서 가장 큰 값과 비교하여 둘 중 최종적으로 큰 값을 리턴하면 된다.

내 코드

class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        res = max(nums)
        curMin, curMax = 1,1

        for n in nums:
            if n ==0:
                curMin, curMax = 1, 1
                continue
            
            tmp = curMax * n
            curMax = max(tmp, n*curMin, n)
            curMin = min(tmp, n*curMin, n)
            res = max(res, curMax)
        return res
    

증빙

여담

코테 할 때 생각보다 그림을 먼저 그려야 한단말이지
화가인가 ?