将环转换为普通数组思考:
- 当目标是越过了末尾的环中子串,找到普通数组中和为负的最小子串,用和减去
- 找普通和最大的子串
- 两者比较取更大
- 特殊情况:
- 全负or全0:输出最大数
- 全正,直接取和
n=eval(input())
a=list(map(int,input().split()))
dp1=[0]*n # 最小
dp2=[0]*n # 最大
dp1[0]=dp2[0]=a[0]
for i in range(1,n):
dp1[i]=min(dp1[i-1]+a[i],a[i])
dp2[i]=max(dp2[i-1]+a[i],a[i])
temp1=min(dp1)
if temp1<0: #非全正
temp1=sum(a)-temp1
temp2=max(dp2)
if temp2<=0: #全负or全0
print(temp2)
else:
print(max(max(dp2),temp1))