[LeetCode] 152. Maximum Product Array

*알고리즘 스터디에 참여하면서 Blind 75 LeetCode Questions 목록에 있는 문제를 풀이합니다.
https://leetcode.com/problems/maximum-product-subarray/

Maximum Product Subarray - LeetCode

문제 해설

숫자 배열이 주어지고, 연속되고 빈 배열이 아닌 부분 배열 중 곱의 값이 가장 큰 것을 찾아 return 한다.
앞서 해설했던 53. Maximum Subarray와 다른 점은 곱셈을 할 때 음수가 있을 때를 고려해야 한다.

---

풀이 - (1) Kadane's Algorithm

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        ans = maxSub = minSub =  nums[0]
        
        for num in nums[1:]:
            if (num < 0):
                tmp = maxSub
                maxSub = minSub
                minSub = tmp
            
            maxSub = max(num, maxSub * num)
            minSub = min(num, minSub * num)
            
            ans = max(ans, maxSub)
            
        return ans

배열을 한 번 탐색하므로 이 방법의 시간 복잡도는 O(N)이다.