Leet code 152 - Maximum Product Subarray

기가 막힌 문제다.. 53번 최대 부분합 문제의 응용버전이다.

 

---

1. s와 e의 범위를 조정하는 최악의 브루트포스

def maxProduct(self, nums:List[int]) -> int:
	max_prod = nums[0]
    	for s in range(len(nums)):
        	for e in range(s, len(nums)):
            	prod = 1
                for i in range(s, e + 1):
                	prod *= nums[i]
                    
                max_prod = max(prod, max_prod)
                
        return max_prod

for 문으로 시작인덱스와 끝 인덱스를 정해준뒤 , 요소 하나하나 전부 순회하며 곱해준다. O(n^3)

---

2.인덱스를 정해주지 않고 누적으로 계속 곱해가는 브루트 포스.

def maxProduct(self, nums:List[int]) -> int:
	max_prod = nums[0]
    	for s in range(len(nums)):
        	prod = 1
        	for n in range(s, len(nums)):
            	prod *= n
     			max_prod = max(prod, max_prod)
                
        return max_prod

O(n^2)

---

3. 동적 프로그래밍. 카데인알고리즘 응용

class Solution:
    def maxProduct(self, nums: List[int]) -> int:

    

        result = nums[0]
        min_prod = max_prod = 1
        
        for n in nums:

            max_prod, min_prod = (
                max(max_prod * n , min_prod * n, n),
                min(max_prod * n , min_prod * n, n)
            )
            result = max(result,max_prod)

        return result

시간복잡도 O(n)

 

한번 순회로 끝난다.

 

부분합을 구해줄때는 , 앞이 음수가 되거나, 이전까지의 부분합이 현재값보다 작을때 초기화해주는 방법을 썼다.

 

한번 순회로 끝내기 위해서, 저장하고 판단해줘야 하는 값은 뭐가 있을까?

 

1. 이전 위치의 최소곱 X 현재 위치의 최소곱

2. 이전 위치의 최대곱 X 현재 위치의 최대곱

3. 현재 위치의 값.

 

최대값을 구하는 문제인데 왜 최소값을 저장해야하나, 의문이 생길 수 있다. 하지만 , 음수라는 부호하나가 최대 최소값 자체를 바꿔버릴 수 있어서 그렇다.

 

예를들어 누적 최소값 -1000이 있다고 해보자. 여기에 다음값으로 -1만 와줘도, 단숨에 1000으로 바뀔 수가 있다.

 

즉 이전의 최소값이였다고 무시하고 버릴게 아니라, 계속 저장하고 있어야 한다.

 

다음단계로의 연산을 위해, 저 세가지 중에서, 최소값과 최대값을 판단하고 , 계속 갱신해줘야 한다. 물론 그중에 최대값이 나오는것은 result로 계속 갱신해준다.