class Solution:
    def FindGreatestSumOfSubArray(self , array: List[int]) -> int:
        best = array[0]
        sum_cum = 0
        for i in range(len(array)):
            sum_cum = max(sum_cum+array[i], array[i])
            best = max(best, sum_cum)
        return best

动态规划：

分治策略 (divide-and-conquer) 的子问题是相互独立的；但动态规划的子问题可以是相关的。后者的艺术就是找出什么是子问题，以及子问题之间的递归方程——即找出状态是什么，以及状态转移方程，这是问题的切入点，也是最难的地方。

所谓的状态转移方程，利用了一条性质：当前问题的最优解，可以由它的子问题的最优解得到。

在该问题中，设数组前 个元素的连续子数组最大和为 Sol(i)，这就是子问题；

可以找到如下递归关系： Sol(i+1) = max(Sol(i)+array[i+1], array[i+1])

【要么和前面的最优解接起来，要么重新开始】

利用递归关系求出 Sol(n) 即可

优化

Sol(i) 可以不存储，题目中在迭代中对它（ sum_cum ）进行更新。

注：

动态规划问题中，有时为了避免重复计算，会存储 sub-problem 的最优解。