33OJ
登录 注册

#S0003. 区间反转

区间反转

题目描述

给你一个长度为 nn 的整数序列,第 ii 个数为 aia_i 。你可以恰好选择一个区间进行区间反转。即将al,al+1,...,ara_l,a_{l+1},...,a_r 变为 ar,ar−1,...,ala_r,a_{r-1},...,a_l 。

现在要求反转后,整个序列的最大子段和。(子段非空)

输入格式

一个数 nn。

nn 个数 aia_i 。

输出格式

反转后,整个序列的最大子段和。

5
2 -1 -3 4 -2
6
3
-1 -2 -3
-1

数据规模与约定

对于 100%100\% 的数据,1≤n≤5000,−104≤ai≤1041 \le n \le 5000,-10^4\le a_i\le 10^4。