최대 부분 수열

시간 제한2초메모리 제한1024 MB

요약

길이 16 이하인 수열을 재배열해 최대 연속 부분합을 가장 작게 만들고, 그 최솟값을 출력한다.

문제

수열 $a_{1...n}$ 에 대해 $f(a)$ 를 다음과 같이 정의한다.

$f(a) = \max\limits_{1 \le l \le r \le n} \sum\limits_{i = l}^{r} a_i\text{.}$

수열 $b_{1...n}$ 이 주어질 때, $b_{1...n}$ 을 순열로 재배열하여 $b'_{1...n}$ 을 만들고 $f(b')$ 을 최소화하려고 한다.

첫째 줄에 정수 $n$ 이 주어진다. ( $1 \le n \le 16$ )

둘째 줄에 $n$ 개의 정수 $a_{1...n}$ 이 주어진다. ( $|a_i| \le 10^5$ )

가능한 $f(b')$ 의 최솟값을 출력한다.