题解 | #连续子数组的最大和(python两种解法)#

（一）解法一——穷举法
（存在重复计算，效率比较低，但是容易理解）
1.思路
对于数组[1,-2,3,10,-4,7,2,-5]，其连续和值最大对应的数组的右边界一定为数组中的某一个元素，所以可以使用for循环遍历这个元素。右边界确定之后，对于左边界则是使用另一个for循环穷举出所有的可能性。最终在所有的值中选出最大值即可。
2.代码
class Solution:

def FindGreatestSumOfSubArray(self, array):
    # write code here
    li=[]
    for i in range(1,len(array)+1):
        for j in range(i):
            count=0
            for m in range(j,i):
                count+=array[m]
            li.append(count)
    return max(li)

（二）解法二——动态规划法
（效率较高，但是本人不是很理解，只能试着解释一下）
1.思路
对于数组[1,-2,3,10,-4,7,2,-5]，其连续和值最大对应的数组的右边界一定为数组中的某一个元素，所以可以使用for循环遍历这个元素。用dp[i]来表示以第i个元素为右边界时的最大连续和的值：
比如，以1为右边界时，dp[0]=1；
以-2为右边界时，dp[1]=-1;
......
当我们在计算以第i个数为右边界时，如果当以第i-1个数为右边界时，连续数组和dp[i-1]<0，即dp[i-1]+array[i]<array[i],那么以i元素为右边界的连续和最大值为array[i]。（dp[i-1]的定义是包括以i-1自己单独考虑的情况的）。否则，dp[i]=dp[i-1]+array[i]。
2.代码
class Solution:

def FindGreatestSumOfSubArray(self, array):
    # write code here
    dp=[0]*len(array)
    dp[0]=array[0]
    for i in range(1,len(array)):
        if dp[i-1]+array[i]<array[i]:
            dp[i]=array[i]
        else:
            dp[i]=dp[i-1]+array[i]
    return max(dp)