[알고리즘] LeetCode - 152 : Maximum Product Subarray

---

📋 문제

Maximum Product Subarray - LeetCode

 

 

 

---

 

📙 풀이

 

연속된 배열의 수를 곱했을 때 최대가 되는 배열의 결과를 찾는 문제이다.

 

음수와 양수를 구분해서 

음수 * 음수 = 양수

양수 * 음수 = 음수

등을 구별하는 것이 관건이다.

 

max_prod, min_prod, ans = nums[0], nums[0], nums[0]
for i in range(1, len(nums)):
    x = max(nums[i], max_prod * nums[i], min_prod * nums[i])
    y = min(nums[i], max_prod * nums[i], min_prod * nums[i])
    max_prod, min_prod = x, y
    ans = max(max_prod, ans)
print(ans)