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

class Solution:
    def FindGreatestSumOfSubArray(self , array: List[int]) -> int:
        # write code here
        # 贪心算法
        # cur = 0
        # res = -1e5
        # for i in range(len(array)):
        #     if cur < 0:
        #         cur = array[i]
        #     else:
        #         cur += array[i]
        #     res =max(res, cur)
        # return res

        # 动态规划
        dp = [0 for i in range(len(array))]
        dp[0] = array[0]
        for i in range(1, len(array)):
            dp[i] = max(array[i], dp[i-1]+array[i])
        return max(dp)