[leetcode][152] Maximum Product Subarray

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

---

정수형 배열 nums가 주어질때, subarray의 원소들의 곱 중 최대를 구해라.

---

곱한다고 했을 때, 최대값이 될 가능성이 있는 경우는

현재 탐색중인 원소가 양수인 경우 가장 큰 양수를 곱하는 경우이고.

탐색중인 원소가 음수인 경우 가장 작은 음수를 곱하는 경우이다.

즉, 배열을 탐색해나가면서 원소의 곱이 가장 큰 경우와 가장 작은 경우를 변수에 저장해둔다.

 

// let, now = 탐색중인 원소 값
// let, maxProducts = 연속되는 원소들의 곱들 중 최대
// let, minProducts = 연속되는 원소들의 곱들 중 최소

maxProducts = max(now, maxProducts x now, minProducts x now)
minProducts = min(now, maxProducts x now, minProducts x now)

점화식은 위와 같다.

탐색하면서 계산되는 maxProducts들 중 최대 값이 정답이 된다.

음수도 있으므로 maxProducts, minProducts는 0으로 초기화하지 않고 입력 배열 요소들 중 하나의 값으로 한다.

 

메모리(최대, 최소 2개 변수 사용)로 문제를 최적화했으므로 DP 문제.

시간복잡도는 O(N).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/152.%20Maximum%20Product%20Subarray.cpp