Python으로 푸는 LeetCode 152. Maximum Product Subarray (Medium)

인접한 원소들과 곱셈(product)을 했을 때, 가장 큰 결과값을 반환하도록 코드를 짜야한다.

LeetCode에서 푼 문제 리스트 보기

LeetCode에서 문제 보기

Github에서 코드 보기

문제 풀이

이 문제는 곱셉을 할 수 있는 모든 가능성을 구하기 위하여 list의 범위를 특정짓는 방법으로 2중 for문으로 순회를 하여 풀 수도 있다.(각각의 for문의 값은 시작 Index와 끝 Index) 다만, Time Limit Exceeded가 나온다. Input 값이 매우매우 클 수도 있기 때문에 이미 예상된 결과이기도 하다.

주어진 Input의 list에는 음수의 값도 포함되어 있기 때문에, (음수*음수)는 양의 정수가 되고 이  값이 최대값이 될 수도 있다는 점을 놓쳐서는 안된다. 따라서 음수와 음수가 만나 최댓값이 될 경우의 수를 포함해 결과값을 비교하기 위해 지금까지의 곱셈의 결과값 중에 가장 최소인 결과값과 가장 최대인 결과값을 다음 원소와 곱해나가면서 최대 결과값을 구해내면 된다. 아래의 코드를 돌려보면 이해하기 더 쉽다. 코드는 LeetCode discuss에서 올려주신 분의 코드를 추가하였다. 

파이썬 코드 - Time Limit Exceeded

from functools import reduce
 
class Solution:
    def maxProduct(self, nums):
        maximum = nums[0]
        for i in range(len(nums)):
            for j in range(i, len(nums)):
                maximum = max(maximum, reduce(lambda x, y: x * y, nums[i:j+1]))
        return maximum
 

파이썬 코드 - 최대값과 최솟값 활용

class Solution:
    def maxProduct(self, nums):
        maximum = big = small = nums[0]
        for n in nums[1:]:
            big, small = max(n, n * big, n * small), min(n, n * big, n * small)
            maximum = max(maximum, big)
        return maximum