/
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 333 点
問題文
高橋君はある店舗の日次損益データを分析しています。黒字の日もあれば、赤字の日もあります。
高橋君は N 日間の損益データを持っており、i 日目(1 \leq i \leq N)の損益は B_i 円です。B_i が正のとき黒字、負のとき赤字、0 のとき損益なしを表します。
高橋君は、1 日目から k 日目までのデータの中から連続する 1 日以上の区間を 1 つ選び、その区間内の損益の合計が最大となる値を求めたいと考えています。これを各 k = 1, 2, \ldots, N について求めてください。
すなわち、各 k = 1, 2, \ldots, N について、次の値を求めてください。
\max_{\substack{1 \leq l \leq r \leq k \\ l, r \text{ は整数}}} \sum_{i=l}^{r} B_i
ここで、1 \leq l \leq r という条件から、選ぶ区間には必ず 1 日以上が含まれます。空の区間は選べないため、すべての日が赤字の場合であっても、必ずいずれかの区間を選ばなければなりません(答えが負の値になることもあります)。
制約
- 1 \leq N \leq 2 \times 10^5
- -10^9 \leq B_i \leq 10^9
- 入力はすべて整数である。
入力
N B_1 B_2 \ldots B_N
- 1 行目には、日数を表す整数 N が与えられる。
- 2 行目には、各日の損益を表す N 個の整数 B_1, B_2, \ldots, B_N がスペース区切りで与えられる。
出力
N 行出力してください。k 行目(k = 1, 2, \ldots, N)には、1 日目から k 日目までのデータにおける、連続する 1 日以上の区間の損益の合計の最大値を整数で出力してください。
入力例 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
Score : 333 pts
Problem Statement
Takahashi is analyzing daily profit and loss data for a certain store. Some days are profitable, while others result in losses.
Takahashi has profit and loss data for N days, where the profit/loss on day i (1 \leq i \leq N) is B_i yen. When B_i is positive, it represents a profit; when negative, a loss; and when 0, neither profit nor loss.
Takahashi wants to select a contiguous subarray of one or more days from the data of days 1 through k, and find the maximum possible sum of profit/loss within that subarray. Determine this for each k = 1, 2, \ldots, N.
In other words, for each k = 1, 2, \ldots, N, find the following value:
\max_{\substack{1 \leq l \leq r \leq k \\ l, r \text{ are integers}}} \sum_{i=l}^{r} B_i
Here, the condition 1 \leq l \leq r ensures that the chosen subarray contains at least one day. Since an empty subarray cannot be chosen, even if all days result in losses, some subarray must still be selected (the answer may be a negative value).
Constraints
- 1 \leq N \leq 2 \times 10^5
- -10^9 \leq B_i \leq 10^9
- All input values are integers.
Input
N B_1 B_2 \ldots B_N
- The first line contains an integer N representing the number of days.
- The second line contains N integers B_1, B_2, \ldots, B_N separated by spaces, representing the profit/loss for each day.
Output
Print N lines. On the k-th line (k = 1, 2, \ldots, N), print the maximum sum of profit/loss over a contiguous subarray of one or more days, considering the data from day 1 through day k, as an integer.
Sample Input 1
5 3 -1 4 -2 5
Sample Output 1
3 3 6 6 9
Sample Input 2
4 -5 -3 -7 -2
Sample Output 2
-5 -3 -3 -2
Sample Input 3
10 2 -3 5 -1 6 -4 2 3 -8 7
Sample Output 3
2 2 5 5 10 10 10 11 11 11
Sample Input 4
20 10 -4 3 -2 8 -15 20 -3 5 1 -7 12 -6 4 9 -1 3 -20 15 6
Sample Output 4
10 10 10 10 15 15 20 20 22 23 23 28 28 28 35 35 37 37 37 38
Sample Input 5
1 -1000000000
Sample Output 5
-1000000000