합의 곱의 절댓값의 최댓값

시간 제한1초메모리 제한256 MB

요약

정수 배열에서 서로 겹치지 않는 구간을 최대 K개 고를 때, 구간 합들의 곱의 절댓값이 가장 큰 값을 구합니다.

문제

수학에는 정말 아름다운 기호가 많다. 수학나라의 수학왕은 특히 합, 곱, 절댓값을 좋아한다. 수학왕은 당신에게 다음의 문제를 냈다.

길이 $N$ 인 정수로 이루어진 수열 $A$ 가 주어진다. 그 뒤, 서로 겹치지 않게 $K$ 개 이하의 구간을 잡는다. 이때, 각 구간의 길이는 $1$ 이상이어야 한다.

구간의 개수를 $X(\ge 1)$ 개 라고 하고, $i$ 번째 구간의 원소의 합을 $S_i (i = 1, 2, \cdots, X)$ 라 하자. 이때 $\left\vert S_1 S_2 \cdots S_X \right\vert$ 의 최댓값은 무엇인가?

수학왕에게 인정받기 위해 문제를 해결하자!

첫 번째 줄에 $N, K$ 가 주어진다.

이후 $N$ 줄에 걸쳐 $i + 1$ 번째 줄에 $A_i$ 가 주어진다.

첫 번째 줄에 $K$ 개 이하의 구간을 잡았을 때의 최댓값을 출력한다.