[leetcode] 152. Maximum Product Subarray

문제 설명

링크
곱했을 때 가장 큰 값이 되는 연속적인 부분 배열 구하는 문제

접근 1 - 2번 scan

• 왼쪽 -> 오른쪽
• 오른쪽 -> 왼쪽
• 0을 만나면 1로 초기화
• 음수 * 음수 = 양수!

코드 1

    def maxProduct(self, nums: List[int]) -> int:
        ans = float('-inf')
        res = 1
        for n in nums:
            res *= n
            ans = max(ans, res)
            if res == 0:
                res = 1
        res = 1
        for n in reversed(nums):
            res *= n
            ans = max(ans, res)
            if res == 0:
                res = 1
        return ans

접근 2 - 카데인(kadane) 알고리즘

• 더했을때 가장 큰수가 나오는 연속된 부분을 찾기 위함
• max 와 min 동시에 갱신 -> min 이 max 가 될수도있기 때문

코드 2

    def maxProduct(self, nums: List[int]) -> int:
    	global_max = prev_max = prev_min = nums[0]
        for num in nums[1:]:
            curr_min = min(prev_max*num, prev_min*num, num)
            curr_max = max(prev_max*num, prev_min*num, num)
            global_max= max(global_max, curr_max)
            prev_max = curr_max
            prev_min = curr_min
        return global_max