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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param array int整型一维数组 
# @return int整型
#dp数组解法
#有几个坑 dp[i] 有两种「选择」，要么与前面的相邻子数组连接，形成一个和更大的子数组要么不与前面的子数组连接，自成一派，自己作为一个子数组。
class Solution:
    def FindGreatestSumOfSubArray(self , array: List[int]) -> int:
#dp[i]为到下标i为止最大连续子数组
        dp=[0 for i in range(len(array))]
        dp[0]=array[0]
        for i in range(1,len(dp)):
            dp[i]=max(dp[i-1]+array[i],array[i])
        maxnum=dp[0]
        for i in range(1,len(dp)):
            maxnum=max(maxnum,dp[i])
        return maxnum