- 首先,先求出原数组的前缀和数组s
- 然后求出$sum[0,n)-2(sum[x,y)+sum[z,n))$的最大值
- 相当于求$sum[x,y)+sum[z,n)$的最小值、
-
即为求$s[y]-s[x]+s[n]-s[z]$的最小值 ($s[n]$是固定值,不用考虑)
-
枚举y,对每个y,从前和后同时遍历,找出两个方向上的最大值
- 求出最小的 $s[y]-s[x]-s[z] $
- 需要全程记录下标,以便输出,并在最值发生改变的时候更新下标
from itertools import accumulate
from math import inf
n = int(input())
arr = list(map(int, input().split()))
s = [0] + list(accumulate(arr)) # accumulate求前缀和
res = (0, 0, 0)
mini = inf
for j in range(n + 1):
max1 = max2 = -inf # inf正无穷,-inf负无穷
idx1, idx2 = 0, 0
for i in range(n):
if i <= j and max1 < s[i]:
max1, idx1 = s[i], i
if i + j <= n and max2 < s[n - i]:
max2, idx2 = s[n - i], n - i
if mini > s[j] - max1 - max2:
res = (idx1, j, idx2)
mini = s[j] - max1 - max2
print(' '.join(str(x) for x in res))