#489. 小码君的实验室2

小码君的实验室2

题目描述

今日小码君的天气实验室又发现新的问题,观测到某地温度有了一段神奇的变化,小码君决定立即派遣UN小码王促进会作为敢死队去检测这部分的温度,在损失了几个成员之后,小码君终于拿到了这段时间的温度变化,现在他需要计算出这段温度中的奇点,所谓奇点就是,在这段连续的温度数值中,需要找到其中连续且非空的一段使得这段温度和最大。(注:温度可能为负数)

输入格式

第一行是一个整数,表示获取到的温度数量 nn。 第二行有 nn 个整数,第 ii 个整数表示温度中的第 ii 个数字 aia_i

输出格式

输出一行一个整数表示答案。

样例

输入样例

样例输入1

7
2 -4 3 -1 2 -4 3

样例输出1

4

数据范围与提示

样例 1 解释

选取 [3,5][3, 5] 子段 {3,1,2}\{3, -1, 2\},其和为 44

数据规模与约定

  • 对于 40%40\% 的数据,保证 n2×103n \leq 2 \times 10^3
  • 对于 100%100\% 的数据,保证 1n2×1051 \leq n \leq 2 \times 10^5104ai104-10^4 \leq a_i \leq 10^4