1424: Greedy
内存限制：32 MB
时间限制：3.000 S
评测方式：文本比较
命题人：
提交：27
解决：5
题目描述
那时我们有梦，关于文学，关于爱情，关于表达式的最大值，如今我们深夜饮酒，杯子碰到一起，都是梦破碎的声音……
那么问题来了，一个只有加号和减号的表达式，你可以在任意位置加上括号，当然也可以加不止一个括号
问如何才能使得这个表达式的值最大
那么问题来了，一个只有加号和减号的表达式，你可以在任意位置加上括号，当然也可以加不止一个括号
问如何才能使得这个表达式的值最大
输入
多组测试数据
对于每组测试数据，先输入一个正整数n（n≤120）
然后输入n个数字以表示表达式中的每一项
举个例子：7 2 -5 6 -4 8 对应的表达式就为7+2-5+6-4+8
对于每组测试数据，先输入一个正整数n（n≤120）
然后输入n个数字以表示表达式中的每一项
举个例子：7 2 -5 6 -4 8 对应的表达式就为7+2-5+6-4+8
输出
输出表达式的最大值（保证答案在int范围内）
样例输入 复制
5
1 2 3 4 5
5
1 2 3 -4 -2
样例输出 复制
15
4
提示
对于样例1：1+2+3+4+5 = 15（不需要加任何括号，当然你也可以在任何地方加括号，最后答案都是15）
对于样例2：1+2+3-(4-2) = 4
对于样例2：1+2+3-(4-2) = 4