题解 | 环形数组的连续子数组最大和

import sys

# 9:55

# 两种情况
# 1 最大值不过环，按正常线性数组来求
# 2， 最大值过环，这个连续过环的数组的和，等于整个数组的和减去这个环头和尾的和，相当于最大的过环连续子数组和，等于整个数组的和，
# 减去线性里连续的子数组的最小和。 
# 特殊情况 (1) 如果数组全为负数，要求非空，那么此时最大值为max(nums)
# (2) 如果数组全为正数，此时最大值为整体和，这个可以处理，主要需要处理一下情况（1）

n = int(input())

nums = list(map(int, input().split()))
total = sum(nums)

dp1 = [0] * (n+1) # 以i结尾的连续子数组和的最大值
dp2 = [0] * (n+1) # 以i结尾的连续子数组和的最小值

dp1[0] = - 10**4 -1
dp2[0] = 10 ** 4 + 1
for i in range(1,n+1):
    dp1[i] = max(dp1[i-1]+nums[i-1],nums[i-1])
    dp2[i] = min(dp2[i-1]+nums[i-1],nums[i-1])

if max(nums)<=0 : # 不能为全负or0   ，
    print(max(dp1))
else:
    print(max(max(dp1),total-min(dp2)))