题目：一个有n个元素的数组，这n个元素即可以是正数也可以是负数，数组中连续的一个或多个元素可以组成一个连续的子数组，一个数组可能有多个这种连续的子数组，求子数组和的最大值。例如，arr = [1, -2, 4, 8, -4, 7, -1, -5]，则最大和的子数组为[4, 8, -4, 7]，最大值为15。
分析：重复利用已经计算的子数组和。Sum[i, j] = Sum[i, j - 1] + arr[j]，在计算Sum[i, j]的时候可以使用前面已经计算出的Sum[i, j - 1]而不需要重新计算，采用这种方法可以省去计算Sum[i, j - 1]的时间，从而提高程序的运行效率。时间复杂度为O(n**2)
code：
def maxSubArr(arr):
if arr is None or len(arr) < 1:
print("参数不合法")
return
res = arr[0]
Sum = arr[0]
i = 0
while i < len(arr):
if Sum > 0:
Sum += arr[i]
else:
Sum = arr[i]
if Sum > res:
res = Sum
i += 1
return res
if __name__ == "__main__":
arr = [1, -2, 4, 8, -4, 7, -1, -5]
print(maxSubArr(arr))
程序运行结果为：
15
