分数: 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