牛客网地址：https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484?tpId=295&tqId=23259&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page

动态规划BM72：

题目如下：

Python实现代码如下：

#
# @param array int整型一维数组
# @return int整型
#
from typing import List


class Solution:
    def FindGreatestSumOfSubArray(self , array: List[int]) -> int:
        length = len(array)
        # 处理特殊情况，数组长度为1时，数组第一个值即为最大值，直接输出
        if length == 1:
            return array[0]

        # 数组长度大于1，用辅助数组，辅助数组与入参数组相同
        help_array = [array[i] for i in range(length)]

        # 动态规划
        for i in range(1, length):
            # 辅助数组当前位置的值更新为：max（当前位置的值，前一个位置+当前位置的值）
            help_array[i] = max(help_array[i-1] + array[i], help_array[i])
        
        # 辅助数组中的最大值即为结果
        return max(help_array)


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

        本题使用动态规划法实现。使用辅助数组，详情见上述代码注释。

        动态规划（Dynamic Programming, DP）是一种通过将问题分解为子问题来优化递归计算的算法设计方法。转移方程是动态规划的核心，用于描述子问题之间的关系，从而将原问题的解通过子问题的解递推出来。上述题目的动态规划的状态转移方程为：help_array[i] = max(help_array[i-1]+array[i], help_array[i])。