← 返回题目列表

AtCoder · awc0074_b

B. 连续子数组的最大和

中文机器翻译题面 查看原题

分数: 333 分

问题陈述

高桥正在分析某个序列。

他被给予了一系列 N 整数 A_1, A_2, \ldots, A_N。高桥想要选择一个 连续子数组 从此序列中,使其元素之和最大化。

具体来说,他选择了一对整数 (l, r) 满意 1 \leq l \leq r \leq N,并计算子数组和 A_l + A_{l+1} + \cdots + A_r.

也允许不选择任何元素(即选择一个空子数组),在这种情况下,总和定义为 0.

找出所有可能选择中的最大总和。

约束

  • 1 \leq N \leq 2 \times 10^5
  • -10^9 \leq A_i \leq 10^9
  • 所有输入值均为整数。

输入

N
A_1 A_2 \cdots A_N
  • 第一行包含一个整数 N,表示序列中元素的数量。
  • 第二行包含整数 A_1, A_2, \ldots, A_N,表示序列的元素,以空格分隔。

输出

打印连续子数组的最大和(或 0 在空子数组的情况下)在单行上。


示例输入 1

5
3 -1 4 -2 2

示例输出 1

6

示例输入 2

8
-2 1 -3 4 -1 2 1 -5

示例输出 2

6

示例输入 3

10
-5 -3 -1 -2 -4 -6 -1 -8 -2 -7

示例输出 3

0