小 Z 的最大子段和(Bounded Max Subarray Sum)

题目描述

小 Z 学习了最大子段和问题，就是给出一个序列，要找到这个序列中连续并且非空的一段，使得这一段的和最大。小 Z 现在当然会求最大子段和了。

小 Y 见小 Z 因为学到的新知识而洋洋得意，立马变换了一下这个问题。现在有 $n$ 个元素的序列 $a_1,a_2,\cdots,a_n$，小 Y 每一次都会删除这个序列中的一个数 $a_i$，问小 Y 每一次删除后，剩余序列的最大子段和是多少。

小 Z 只会最简单的最大子段和，对于小 Y 的这个问题他只能求助于你。

输入格式

第一行输入一个整数 $n$，表示序列元素的个数。

第二行输入 $n$ 个自然数 $a_1,a_2,\cdots,a_n$。

输出格式

输出一行共 $n$ 个整数，表示小 Y 每次删除 $a_i$ 后剩余序列的最大子段和。

样例输入 #1

5
1 6 -100 4 5

样例输出 #1

9 9 16 7 7

样例输入 #2

10
493 592 620 176 389 -807 -2 960 687 762

样例输出 #2

3377 3278 3250 3694 3481 4677 3872 2910 3183 3108

数据范围

【样例 1 解释】

• 删除 $1$，得到序列为 $[6,-100,4,5]$，最大子段序列为 $[4,5]$ 最大子段和为 $9$。
• 删除 $6$，得到序列为 $[1,-100,4,5]$，最大子段序列为 $[4,5]$ 最大子段和为 $9$。
• 删除 $-100$，得到序列为 $[1, 6, 4, 5]$，最大子段序列为 $[1,6,4,5]$ 最大子段和为 $16$。
• 删除 $4$，得到序列为 $[1,6,-100,4]$，最大子段序列为 $[1,6]$ 最大子段和为 $7$。
• 删除 $5$，得到序列为 $[1,6,-100,4]$，最大子段序列为 $[1,6]$ 最大子段和为 $7$。

【数据范围】

对于 $30\%$ 的数据，$n\leq 100$

对于 $60\%$ 的数据，$n\leq 1000$

对于 $100\%$ 的数据，$1< n\leq 10^5,|a_i|\leq 10^9$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1400。

测试点分布

出处：原题链接