题目：输入一个整型数组，数组中有整数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。
解析：令f(i)代表以第i个数字结尾的子数组的最大和，那么我们可以求出所有的最大和，然后求max(f[i])。如果上一个数之前的子数组和小于0，则到当前的数的子数组的和为当前数的大小；如果上一个数之前的子数组和大于0，则到当前的数的子数组的和为当前数的大小加上一子数组的和。递归公式如下：
代码如下：
# -----------动态规划-------------
def FindGreatestSumOfSubArray_dp(arr):
global g_InvalidInput
if arr == None or len(arr) <= 0:
g_InvalidInput = True
return 0
g_InvalidInput = True
opt = [0] * len(arr)
opt[0] = arr[0]
for i in range(1, len(arr)):
if opt[i-1] <= 0:
opt[i] = arr[i]
else:
opt[i] = arr[i] + opt[i-1]
return max(opt)
