题解 | #连续子数组最大和#

import sys

"""
用前缀和做，时间复杂度为o(n^2),在本题中会超时
下面是动态规划解决，时间复杂度为o(n),解决超时问题
n = int(input())
l = list(map(int, input().split()))
for i in range(1, len(l)):
    l[i] = l[i - 1] + l[i]
if n == 1:
    print(l[0])
else:
    dp = [l[0]]
    for i in range(1, len(l)):
        dp.append(l[i])
        for j in range(i):
            dp.append(l[i] - l[j])
    print(max(dp))
"""
n = int(input())
l = list(map(int, input().split()))

# 创建初始化值为负无穷大的数组
dp = [0] * n

# 初始化数组第一个元素,值为l[0]
dp[0] = l[0]

for i in range(1, n):
    # 从第二个元素开始判断，如果该元素的前一个元素和大于零，则相加
    if dp[i - 1] > 0:
        dp[i] = dp[i - 1] + l[i]
        # 否则，将初始和跟更新为当前元素本身
    else:
        dp[i] = l[i]
print(max(dp))