#P3369. [Usaco2004 Feb]Pesky Parentheses 烦人括号

    ID: 2558 传统题 1000ms 512MiB 尝试: 18 已通过: 9 难度: 4 上传者: 标签>CF1500普及+/提高-区间 DP枚举最后一次操作添加哨兵Orange

[Usaco2004 Feb]Pesky Parentheses 烦人括号

题目描述

奶牛们只学过加和减.她们写下了含有 NN 项的表达式,比如:

1+4−2−1+10−61+4-2-1+10-6

贝茜认识到地加上不同的括号,表达式就会有不同的值。请帮她计算出表达式的最大值。

输入格式

第 11 行:整数 NN;

第 22 到 N+1N+1 行:每行是一个整数 KK,表示表达式中的一项。正整数 KK 表示 +K+K,负整数 KK 表示 −K-K。

输出格式

一个整数,通过适当地加括号使表达示得到的最大值.

6
1
4
-2
-1
10
-6
20

样例解释

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

数据范围与约定

对于 100%100\% 的数据,1≤N≤101 ≤ N ≤ 10,−100≤K≤100-100 ≤ K ≤ 100。

题目来源

Orange