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

求解连续子数组的最大和，问题可以分解为如下步骤：

• 数组长度为0，返回0
• 数组长度为1，返回数组第一个值
• 数组长度大于1，从前往后，判断数组（第i个值+第i-1个值）于（第i个值）的大小，将其中较大值赋值给当前数组的第i个值。即计算数组从第一个值，到第i个值的最大子数组。

def max_sum(n, dp):
    if n == 0:
        return 0
    elif n == 1:
        return dp[0]
    else:
        for i in range(1, n):
                dp[i] = max(dp[i - 1] + dp[i], dp[i])
        return max(dp[:])

n = int(input())
s = input()
s = s.split()
dp = [int(s[i]) for i in range(len(s))]
print(max_sum(n, dp))