문제
풀이
이 문제는 음수와 음수를 곱하면 양수가 된다는 점을 생각해야 합니다.
minProduct(i)는 셋 중 하나를 택해야 합니다.
먼저 직전의 minProduct가 음수이면서 현재 값인 value(i)가 양수라면 이 둘을 곱해서 minProduct가 더 작아질 수 있습니다.
아니면 직전의 maxProduct가 양수이고 현재 값이 음수라면 둘을 곱했을 때 음수가 나오므로 이 역시 가장 작은 값의 후보 중 하나입니다.
그것도 아니라면 이전까지의 결과는 다 버려버리고 그냥 본인만을 유일하게 갖는 subarray가 되어 최솟값의 자리를 차지할 수도 있겠네요.
maxProduct(i) 역시 같은 방법으로 구할 수 있습니다.
minProduct와 maxProduct의 값을 구할 때는 이전의 subarray의 곱에 본인을 곱하거나, 본인 단독으로만 존재하므로 subarray가 연속적이어야 한다는 조건 역시 만족할 수 있습니다.
우리의 maxProduct(i)는 항상 i번째 값을 마지막으로 하는 subarray를 대상으로만 하기 때문에, 정답을 구하기 위해서는 모든 경우의 maxProduct를 대상으로 최댓값을 찾아봐야 합니다.