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

较简单的dp，设dp[i]为以array[i]结尾的子串，达到sum最大，状态转移方程如下式所示：

$dp[i]=max\{array[i],array[i]+dp[i-1]\}dp[i]=max\backslash \{array[i],array[i]+dp[i-1]\; \backslash \}$

然后注意下初始条件就行。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param array int整型一维数组 
# @return int整型
#

import copy

class Solution:
    def FindGreatestSumOfSubArray(self , array) -> int:
        # write code here
        dp = copy.deepcopy(array)
        for i in range(1 , len(array)):
            dp[i] = max(array[i] , dp[i-1]+array[i])
        return max(dp)

array = [1,-2,3,10,-4,7,2,-5]
print(Solution().FindGreatestSumOfSubArray(array))