U414379 过去的项链

**时间限制：** 1.0 秒 **空间限制：** 512 MB

过去有一个项链。这个项链上串了 $N$ 个珠子，其中第 $i$ 个珠子上有 $a_i$ 的能量值（$a_i$ 不一定非负）。 对于一段**连续的珠子**，过去定义其美丽程度为它们的能量值之和。自然地，一个项链的美观值定义为它的**所有非空连续子段**的美丽程度的最大值。 过去得到了一把神奇剪刀，他可以把这个项链的**恰好一个**连续子段剪下来，然后翻转这个子段，再拼接回去得到一个新项链。 过去想利用这把剪刀，得到一个美观值尽可能大的新项链。那么问题来了：请你告诉过去，他的新项链的美观值最大可以是多少。

无

无

### 样例 1 解释 翻转 $a_3, a_4$ 之后，美丽程度的最大值在子段 $[5, 3, 2, 1]$ 上取到，故答案为 $11$ 。 ### 子任务 子任务 1（30 分）：$N \le 50$ 。 子任务 2（25 分）：$N \le 400$ 。 子任务 3（25 分）：$N \le 3000$ 。 子任务 4（20 分）：$N \le 2\times 10^5$ 。