Algorithm

Maximum Product Subarray

by VICENTE97P4

Dec. 19, 2021, 9:02 p.m.

문제 링크: https://leetcode.com/problems/maximum-product-subarray/

LeetCode는 잘 안 쓰는 편입니다.

그런데 이번에 아는 동생이 재미있는 문제를 줘서 풀어보았습니다.

사실 비슷한 문제인 연속된 수열의 최대 합 구하기는 이미 널리 알려진 문제입니다.

그냥 매번 최대값을 비교하여 갱신해주고, 음수가 되면 다시 0을 넣어서 진행해주고..

DP 문제를 많이 안 풀어봐도 자세히 생각해보면 풀 수 있는 문제입니다.

하지만 곱하기는 경우가 다릅니다.

음수가 곱해지는 경우 값이 확 작아지는데, 나중에는 이 값에 또 음수가 곱해져서 최대값이 될 수도 있습니다.

그렇다고 음수를 모두 저장해서 일일히 비교하기에는 N^2이라 TLE가 나고..

결국에는 원사이드하게 진행해서 N이나 NlogN으로 해결해야 하는데 NlogN은 뭐.. 아닌 거 같고..

그럼 어쩌란 거지? 하는 생각이 들기 마련입니다.

실제로 이 문제를 이야기해준 동생은 좌절하여 에듀윌로 가서 공무원을 준비하겠다고 선언하는 지경에 이르렀습니다.

녀셕의 두뇌는 나보다 훨씬 뛰어나고, 대한민국을 이끄는 선두주자가 되기 충분한데..

아무튼 각설하고 풀어봅시다!!

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        ans = nums[0]
        maximum = nums[0]
        minimum = nums[0]
        
        for i in range(1, len(nums)):
            maximum, minimum = max(maximum*nums[i], minimum*nums[i], nums[i]), min(maximum*nums[i], minimum*nums[i], nums[i])
            ans = max(ans, maximum)
            
            
        return ans

답은 간단합니다. 그냥 최소값도 같이 저장해서 들고다니면 됩니다.

배열로 저장할 필요도 없습니다. 그냥 변수에 최대값 하나, 최소값 하나 들고다니면 됩니다.

단, 매 index 비교마다 최대값(ans) 비교는 해줘야 하고, 차라리 끊고 새로 들어온 인덱스부터 시작하는 경우도

고려해줘야 합니다.

왜냐하면 최대, 최소값이 모두 음수일 경우에는 양수로 새로 시작하는게 더 크기 때문입니다.

진짜 아무것도 아닌 문제인데, 생각보다 떠올리기 까다로울 수 있습니다.

이 문제를 못 풀었다 하더라도, 다양한 아이디어를 배워가며 생각의 폭을 넓혀가고, 사색으로 깊이를 깊혀가면 됩니다.

세상 모든 것을 스스로 알아낼 수는 없는 법이니까요..

극복할 수 있는 문제로 좌절하여 총명한 머리를 썩히지 않았으면 합니다.

그 동생도, 그리고 여러분들도..

물론 제가 제일 급하죠. ^^

26 view 614