#1397. 小苯的区间和疑惑

小苯的区间和疑惑

题目描述

帅气的大白熊这天向小苯提出了一个问题,他给了小苯一个长度为 nn 的数组 aa 。

他想知道,对于所有 1≤i≤n1 \leq i \leq n 的下标 ii ,都从数组中选择一段连续的区间 [l,r][l, r] 使得 l≤i≤rl \leq i \leq r ,即选择一个包含 ii 的区间的话,这段区间和最大是几?

请聪明的你帮帮小苯解答吧。

输入格式

输入包含两行。 第一行一个正整数 n(1≤n≤2×105)n (1 \leq n \leq 2\times10^5)。 第二行 nn 个整数 ai(−109≤ai≤109)a_i (-10 ^9 \leq a_i \leq 10^9),表示这个数组。

输出格式

输出包含一行 nn 个整数。 其中第 ii 个整数代表,选择一段包含 aia_i 的区间,这段区间的最大和。

样例

4
1 -2 3 -4
2 2 3 -1
3
-1 -1 -1
-1 -1 -1

题目来源:洛谷 U549625