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

题目：https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484

输入：[1,-2,3,10,-4,7,2,-5]

返回值：18

说明：输入数组的最大和子数组为[3,10,一4,7,2]，因此输出为该子数组的和 18。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param array int整型一维数组 
# @return int整型
#
class Solution:
    def FindGreatestSumOfSubArray(self , array: List[int]) -> int:
        # dp[i]记录到i位置为止的最大和，把每个位置为止的最大和都算一遍，再比较，就可以知道结果
        #注意要求连续数组，dp[i]=max(array[i],dp[i-1]+array[i])意思是如果加上array[i]变小了，那不如直接取array[i]
        #其实不需要dp数组，只要一个记录到i位置为止的最大和的变量就行，用everymaxsum。
        #得到了到i位置为止的最大和，我们还要在过程中把各个位置最大和里面最大的那个取出来，用allmax。
        
        everymaxsum=array[0]
        allmax=array[0]
        for i in range(1,len(array)):
            everymaxsum=max(everymaxsum+array[i],array[i])
            allmax=max(everymaxsum,allmax)
        return allmax
`