Pesky Parentheses

면접 대비

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

요약

부호가 붙은 항들의 수열이 주어질 때, 순서와 덧셈·뺄셈 연산을 지키면서 식의 값을 최대로 만드는 괄호 묶음을 찾는다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 구간, 완전 탐색, 재귀
정답자: 아직 제출이 없습니다

문제

The cows just learned to add and subtract. They've written down an expression containing N terms (1 ≤ N ≤ 10) such as the following:

1 + 4 - 2 - 1 + 10 - 6

Bessie (the smart cow) realizes that this expression can evaluate to different numbers depending on how it is parenthesized. Help her determine the maximum possible number to which it can evaluate.

입력

Line 1: The single integer N
Lines 2..1+N: Each line contains an integer between -100 and 100 (inclusive) and corresponds to one term in the expression. A positive number K corresponds to + K in the expression and a negative number -K corresponds to - K in the expression.

출력

Line 1: The maximum value to which the expression can evaluate, if properly parenthesized.

힌트

1 + 4 - (2 - (1 + 10) - 6) = 20

예제1

예제 1
입력
```
6
1
4
-2
-1
10
-6
```
예상 출력
```
20
```