← 返回题目列表

AtCoder · past202212_g

G. 范围总和

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

问题陈述

给你一个长度的整数序列 N: A = (A_1, A_2, \ldots, A_N).

打印最大可能值 A_l + A_{l+1} + \cdots + A_r 一对 (l, r) 这样 1 \leq l \leq r \leq N.

约束

  • 1 \leq N \leq 2 \times 10^5
  • -10^9 \leq A_i \leq 10^9
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \ldots A_N

输出

打印答案。


示例输入 1

10
-6 5 -3 3 -1 4 -1 5 -9 2

示例输出 1

12

对于 (l, r) = (2, 8),我们有 A_2 + A_3 + \cdots + A_8 = 5 + (-3) + 3 + (-1) + 4 + (-1) + 5 = 12,这是最大可能值。


示例输入 2

3
-1 -2 -3

示例输出 2

-1

示例输入 3

20
-14 74 -48 38 -51 43 5 37 -39 -29 80 -44 -55 59 17 89 -37 -68 38 -16

示例输出 3

176