[Leetcode 아주 상세한 문제풀이] 152. Maximum Product Subarray - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 152번 문제 Maximum Product Subarray 다.

우선 문제를 살펴보자.

 

리트코드 152번 문제 Maximum Product Subarray (링크)

Maximum Product Subarray - LeetCode

Maximum Product Subarray - LeetCode

 

 

Given an integer array nums, find a subarray that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

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

Example 2:
Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Constraints:
1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

 

 

문제 설명

문제에 대해 간략히 살펴보자.

이 문제는 53번 문제 Maximum subarray와 유사하다.

기존 문제는 subarray의 합이 최대가 되는 것을 구하는 문제였다면 이번 문제는 subarray의 곱이 최대가 되는 것을 구하는 문제다.

즉, 주어진 배열안에 음수가 포함될 수 있기 때문에 53번 문제에서 처럼 배열을 처음부터 차례대로 검색하다보면 음수를 만나는 지점에서 갑자기 전체 곱이 음수가 되게 되어버린다.

따라서 배열 내 음수를 어떻게 핸들링하며 최대 곱을 갖는 subarray를 찾는것이 관건이다.

 

 

문제 접근법

이 문제를 푸는 가장 직관적인 방식은 물론 배열 내 모든 subarray를 찾아 그 곱을 구하고 서로 비교해서 최대 곱을 찾는 brute force 방식이라 할 수 있겠다. 하지만 배열 크기가 늘어남에따라 time complexity가 굉장히 커지기 때문에 효율적인 접근방식은 아니라고 할 수 있다.

이 문제는 앞서 풀어봤던 53번 문제 Maximum subarray와 비슷한 방법으로 풀 수 있다.

즉, 배열의 처음 숫자부터 시작해 그 다음 배열의 숫자 하나하나 곱해 나가며 최대 곱을 업데이트 해준다.

이때 중요한 건 음수를 만나게 되는 지점인데, 음수를 곱하게 되면 최대 곱이 최소 곱이 되어버린다.

따라서 이 문제의 핵심은 다음 배열의 숫자를 곱해나가는 과정에서 최대값과 최소값을 추적하는 것이 중요하다.

 

문제 접근 예시

예를 들어 [2, 3, -1, -1]이라는 배열이 주어졌다고 하자.

 

우선 첫번째 숫자 (=2)에 두번째 숫자 (=3)를 곱할 경우 이 subarray [2, 3]의 최대 곱은 6 (=2*3) 최소 곱은 3이 된다. 3이 되는 이유는 우리는 subarray를 찾고 있기 때문에 2를 포기하면 되기 때문이다. 즉, 3에서 새로 시작되는 새로운 subarray를 찾으면 되기 때문에 이 계산에서 얻어지는 최소 곱은 3이 된다.

이 과정을 반복해 나갈 때 음수를 만나게 되면 최대 곱과 최소 곱의 위치를 바꿔주는 것이 중요하다.

 

예를 들어 첫번째 연산 후 최대 곱은 6 최소 곱은 3인데 여기에 배열의 세번째 숫자 -1을 곱하게 되면 최대 곱이 오히려 최소 곱이 되기 때문이다. 우리는 최대 곱을 구하는 것이 목적이기 때문에 세번째 숫자를 곱하기 직전 최대 곱 6과 최소 곱 3의 위치를 바꾸어 준다. 그렇게 되면 -1을 곱한 후 최대 곱은 -3 최소 곱은 -6이 되게 된다.

 

최종적으로 배열의 네번째 숫자 -1을 다시 만나게 되는데, 이때 다시 최대 곱 -3과 최소 곱 -6의 위치를 다시 한 번 더 바꿔 연산을 하게 되면 (*1) 최종적으로 최대 곱은 +6 최소 곱은 +3이 되게 된다.

 

물론 실제 코드에서는 한 가지를 더 고려해줘야 하는데, 배열의 길이가 길어지면 local max product가 생길 수 있기 때문에 항상 local max product끼리 비교하여 global max product를 구하는 것이 필요하다.

 

 

문제 풀이

코드를 한 번 살펴보자.

우선 배열을 입력받을 함수를 정의해 준다 (line 1)

그리고 배열의 길이를 구해주고, 위에서 언급한 최대 곱과 최소 곱을 저장할 변수를 만들어 준다 (line 2-6)

그리고 global max product를 저장할 변수도 만들어 준다 (line 7)

이때 문제의 조건에 따라 최소 배열 길이는 1이므로 위 변수의 초기값은 첫번째 인덱스 값으로 해준다.

변수 지정 후 for loop을 배열 길이만큼 돌려준다 (line 9)

앞서 설명한 것 처럼 배열의 다음 숫자와 곱셈 연산을 했을때 최대 곱과 최소 곱을 구한다 (line 15-16)

그리고 그때의 최대 곱과 global max product를 비교해 더 큰 값을 취한다 (line 19)

이때 중요한 것은 배열에서 음수를 만났을 때인데

이때 앞서 설명한 것 처럼 직전 인덱스에서 구했던 최대 곱과 최소 곱을 서로 바꿔준다 (line 11-12)

최종적으로 global max product를 리턴해준다 (line 21)

 

 

문제 풀이 코드

def maxProduct(nums):
    n = len(nums)
    
    # Initialize variables to keep track of max and min products ending at each position
    max_ending_here = nums[0]
    min_ending_here = nums[0]
    max_product = nums[0]
    
    for i in range(1, n):
        # Swap max_ending_here and min_ending_here if the current number is negative
        if nums[i] < 0:
            max_ending_here, min_ending_here = min_ending_here, max_ending_here
        
        # Update max_ending_here and min_ending_here considering the current number
        max_ending_here = max(nums[i], max_ending_here * nums[i])
        min_ending_here = min(nums[i], min_ending_here * nums[i])
        print("i=", i)
        print(max_ending_here)
        print(min_ending_here)
        
        # Update max_product if max_ending_here is greater
        max_product = max(max_product, max_ending_here)
        print(max_product)
    
    return max_product
 
# Test cases
nums1 = [2, 3, -2, 4]
print(maxProduct(nums1))  # Output: 6
 
#nums2 = [-2, 0, -1]
#print(maxProduct(nums2))  # Output: 0