← 返回题目列表

AtCoder · awc0067_b

B. 损益的最大子数组和

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

分数: 333 分

问题陈述

高桥正在分析某家商店的每日损益数据。有些日子是有利可图的,而另一些日子则是亏损的。

高桥有损益数据 N 天,其中当天的盈利/亏损 i (1 \leq i \leq N)是 B_i 日元。当 B_i 为正数,代表盈利;为负时,表示损失;当 0,既不盈利也不亏损。

高桥想要选择 一天或多天的连续子数组 来自天数的数据 1 通过 k,并找到该子数组中利润/损失的最大可能总和。为每个确定此 k = 1, 2, \ldots, N.

换句话说,对于每个 k = 1, 2, \ldots, N,找到以下值:

\max_{\substack{1 \leq l \leq r \leq k \\ l, r \text{ are integers}}} \sum_{i=l}^{r} B_i

这里,条件 1 \leq l \leq r 确保所选子数组至少包含一天。由于不能选择空的子数组,即使所有天都导致损失,仍然必须选择某些子数组(答案可能是负值)。

约束

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

输入

N
B_1 B_2 \ldots B_N
  • 第一行包含一个整数 N 代表天数。
  • 第二行包含 N 整数 B_1, B_2, \ldots, B_N 以空格分隔,代表每天的盈利/亏损。

输出

打印 N 行。上 k- 第行 (k = 1, 2, \ldots, N),考虑一天中的数据,打印一天或多天的连续子数组的最大利润/损失总和 1 全天 k,作为整数。


示例输入 1

5
3 -1 4 -2 5

示例输出 1

3
3
6
6
9

示例输入 2

4
-5 -3 -7 -2

示例输出 2

-5
-3
-3
-2

示例输入 3

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

示例输出 3

2
2
5
5
10
10
10
11
11
11

示例输入 4

20
10 -4 3 -2 8 -15 20 -3 5 1 -7 12 -6 4 9 -1 3 -20 15 6

示例输出 4

10
10
10
10
15
15
20
20
22
23
23
28
28
28
35
35
37
37
37
38

示例输入 5

1
-1000000000

示例输出 5

-1000000000