#9277. 「第9次PTA认证」星际矿脉能源勘探 普及−

时间限制:1000 ms 内存限制:256 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Wind_Rises

题目描述

在遥远的塞拉芬星系,你是一位经验丰富的星际探险家。最近,你在代号为"X-7B"的未知行星上发现了一条极其罕见的能量矿脉。这条矿脉蕴含着强大的宇宙能源,是

维持星际航行和殖民地运转的关键资源。作为一名专业的能源勘探者,你携带着先进的能源收集器降落到这颗行星表面。矿脉可以抽象为一个线段,由 个连续且相

互不重叠的地段组成,每个地段都有一个特定的能源值:正值表示该地段能源丰富,负值则表示该地段存在能量干扰或消耗区域。你的能源收集器每次启动只能收集若干

连续地段(至少一个地段)的能源,且收集器的效率取决于这段地段的能源总和。由于收集器的能量储备有限,你必须谨慎选择收集区域,以最大化能源获取。

任务目标:请设计一个勘探方案,找出矿脉上连续的一段地段,使得收集器能够收集到的能源总量最大,为你的星际航行提供充足的能源保障。

输入格式

第一行是一个整数 (),表示矿脉地段的个数。

第二行有 个整数,表示每个地段的能源值,每个能源值的绝对值不超过

输出格式

输出一个整数,表示收集器能够收集到的最大能源总量。

样例

样例输入

7
2 -4 3 -1 2 -4 3

样例输出

4

样例解释

选择从第 3 个地段到第 5 个地段,能源值分别为 3、-1、2,总和为 4,这是所有连续地段中能源总量最大的一段。