2060 - 【入门】装饰彩带
Time Limit : 1 秒
Memory Limit : 128 MB
周周有一条彩带，上面有相邻的 n 个不同颜色的区域，每个区域对于装饰效果的影响不一样（影响值有正有负，但总和不会小于 -10000）周周想在上面截取一段，请问最多可以获得多大的装饰效果。
Input
输入有 2 行：
第一行是一个整数 n (1≤ n ≤10000)，表示有 n 个数；
第二行有 n 个空格隔开的整数 a_i。
Output
输出最大的装饰效果。
Examples
Input
6 1 -2 1 -3 5 6
Output
11
Hint
我们可以枚举截取的起点 a 和终点 b，并通过前缀和求出该区间的所有数的和，得到 a、b 之间的装饰效果，再求出最大值就可以啦。
Source
前缀和 动态规划