241465 - 能源勘探(explore)

题目描述

在塞芬星系的X-7C行星上发现了一条能量矿脉,矿脉由n个连续且相互不重叠的地段组成。每个地段有一个能源值(正负值表示能源丰富或消耗)。需要找出连续的一段地段,使得能源总和最大。

输入

第一行:整数 n (1 ≤ n ≤ 2×10⁵),表示地段个数。

第二行:n个整数,表示每个地段的能源值(|能源值|<=1e7)。

输出

一个整数,表示最大能源总量。

样例

输入

7
2 -4 3 -1 2 -4 3

输出

4
说明

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

题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 73
通过人数 22
金币数量 2 枚
难度 基础


上一题 下一题