Python解法：动态规划

'''
dp解法
dp[i]表示到 0-i之间连续最大和
则状态转移方程为： dp[i]=max(array[i],dp[i-1]+array[i])
'''
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        if not array:
            return 0
        n=len(array)
        if n==1:
            return array[0]
        else:
            dp=[0]*n
            dp[0]=array[0]
            for i in range(1,n):
                dp[i]=max(array[i],dp[i-1]+array[i])
            return max(dp)