[Leetcode] 152. Maximum Product Subarray

Jonghae Park·2021년 12월 3일
0

영혼의 알고리즘

목록 보기
13/19

21-12-03
solved, but too iterative

Problems

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

It is guaranteed that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.

Example 1:

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

Max Subarray에서 사용한 Kadane's Algorithm과 비슷한 문제이다. 하지만 음수의 개수에 따라 Max product이 바뀔 수 있다는 점이 까다롭다.

Solution

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        l=len(nums)
        ans=max(nums)
        
        dp=nums.copy()
        
        if nums[0]<0:
            lm=0
        else:
            lm=-1   
        
        for i in range(1,l):
            v=nums[i]
            
            if v<0 and lm==-1:
                lm=i
            
            if dp[i-1]==0:
                continue
                
            if v==0:
                if lm!=-1 and lm!=i-1:
                    ans=max(ans,dp[i-1]//dp[lm])
                lm=-1
                continue
            
            dp[i]=dp[i-1]*v
            ans=max(ans,dp[i])
            
        if lm!=-1 and lm!=l-1:
                ans=max(ans,dp[l-1]//dp[lm])  
    
        print(dp,lm)
        return ans

dp[i]는 i번째 원소로 마지막으로하는 subarray의 누적 product이다. 여기서 lm이 등장하는데 subarray에서 leftmost 음의 element index이다. lm을 구하는 이유는, subarray에서 가장 왼쪽 음수를 포함한 왼쪽 subarray를 제외한 나머지 subarray의 product을 구하기 위함이다.
이 풀이의 단점은 corner case에 취약하다는 점이다. [-1,-2,-3,0] 등 음수가 반복적으로 나오는 상황을 따로 처리해줘야한다.

Best Solution

    if not nums:
            return 0
        
        if len(nums) == 1:
            return nums[0]
        
        min_so_far, max_so_far, max_global = nums[0], nums[0], nums[0]
        for i in range(1, len(nums)):
            max_so_far, min_so_far = max(min_so_far*nums[i], max_so_far*nums[i], nums[i]), min(min_so_far*nums[i], max_so_far*nums[i], nums[i])
            max_global = max(max_global, max_so_far)
        
        return max_global

아이디어가 명확하고 코드가 직관적이다.
다음과 같은 Kadane's Algorithm의 핵심 아이디어가 들어가있다.

global maximum is the larger one between a local maximum and the previous global maximum.

이 문제에서는 특히 min_so_far이 음수를 만나 max_so_far로 업데이트 된다는 특징을 잘 캐치해야한다. 따라서 max_so_far뿐만 아니라 min_so_far도 dp로 tracking한다.

Intuitive Solution

    def maxProduct(self, A):
        B = A[::-1]
        for i in range(1, len(A)):
            A[i] *= A[i - 1] or 1
            B[i] *= B[i - 1] or 1
        return max(A + B)

보다 직관적인 풀이 방법이다. 사실 lm를 두지 않더라도, 오른쪽에서부터 누적 product을 구하고 max 값을 구하면 된다는 아이디어를 가지고 있다. A[i-1]이 0이 되는 경우는 이전 숫자가 1인 것으로 처리해서, A[i]에 그 value만 남기게 해주었다.

profile
알고리즘 정리 좀 해볼라고

0개의 댓글