[LeetCode 풀이/python] 152. Maximum Product Subarray (medium)

문제 설명: 정수 배열 nums 가 주어졌을 때, 하나 이상의 원소가 존재하며 연속하는 부분 배열(subarray) 중 가장 큰 곱을 갖는 배열을 찾아 이 때의 곱셈 값을 리턴하시오. 정답은 32-비트 정수로 표현할 수 있음이 보장되며, 부분 배열은 해당 배열의 연속하는 부분집합이다.

 

(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.)

 

 

예시 1)

입력: nums = [2,3,-2,4]  -->  출력: 6

설명: 부분 배열 [2,3] 은 가장 큰 곱 6 을 만들 수 있다

 

예시 2)

입력: nums = [-2,0,-1]  -->  출력: 0

설명: [-2, -1] 은 연속된 부분 배열이 아니기 때문에 2 는 최대 곱이 될 수 없다

 

제한 조건:

• 1 <= nums.length <= 2 * 10^4
• -10 <= nums[i] <= 10

 

 

------ * ------ * ------ * ------

 

[풀이 1안]  -- w/ solution peeping

• 접근법
  • 이전 부분 배열까지의 합이 negative 이면 새 출발(...) 을 하면 되는 부분 배열 최대 합 문제와 달리, 부분 배열 최대 곱 문제는 이전 부분 배열까지의 곱이 negative 값을 가지더라도 새로이 곱해지는 수가 negative 이면 최대 값이 될 수 있기 때문에 단순히 직전까지의 최대 값 만을 갖고 있으면 안 됨 ! (negative 라고 무작정 버리면 안된다 ~_~)
    • 오히려 negative 인 최소 값이 최대 값을 만들기 위한 부분 요소가 될 가능성이 있음!
  • 이를 고려하면, 어떤 배열의 i 번째 인덱스까지의 부분 배열 array[:i] 이 최대 곱셈 값을 가질 수 있는 경로(방법) 은 아래와 같이 세 가지 존재함
    • 이전까지의 부분 배열 array[:(i-1)] 의 곱이 (max) positive * i 번째 값 array[i] 가 positive
    • 이전까지의 부분 배열 array[:(i-1)] 의 곱이 (min) negative * i 번째 값 array[i] 가 negative
    • i 번째 값 array[i]
  • 이러한 세 가지 경우를 모두 고려하여 최대 곱셈 값을 갱신하기 위해 min_product, max_product 를 모두 변수로 갖고 갱신해나가는 것이 포인트!

 

• 코드 구현

def maxProduct(nums: List[int]) -> int:
    max_prod, min_prod, res = nums[0], nums[0], nums[0]
       
    for i in range(1, len(nums)):
        max_ = max(nums[i], max_prod*nums[i], min_prod*nums[i])
        min_ = min(nums[i], max_prod*nums[i], min_prod*nums[i])
        max_prod, min_prod = max_, min_
        res = max(max_prod, res)

    return res

 

• 결과
  • 배열 nums 를 한 번만 스캔하면 되므로 선형 시간 복잡도 O(n) 을 가짐!
  • 언뜻 복잡해보이지만 코드도 간결하고 넘 재미난 문제...! ㅎ_ㅎ