连续子数组的最大和

问题简述

给定数组 arr，求其连续子数组的最大和。

连续子数组的最大和_牛客题霸_牛客网

思路：动态规划

• 记 dp[i] 表示以 arr[i] 结尾的最大和；

• 则 dp[i] = max(dp[i - 1] + arr[i], arr[i])；

• 因为 dp[i] 只与上一个状态有关，因此可以使用滚动变量优化（详见代码）；

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param array int整型一维数组 
# @return int整型
#
class Solution:
    def FindGreatestSumOfSubArray(self , array: List[int]) -> int:
        # write code here
        ret = dp = array[0]
        for x in array[1:]:
            dp = max(x, dp + x)
            ret = max(ret, dp)
        
        return ret