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

解题思路：

1. 这道题可以考虑使用动态规划来解决，为什么呢？
2. 动态规划：最优子结构和重叠子问题。对于这道题来说，这两个性质都是满足的，首先大问题的最优解包含着小问题的最优解，然后子问题是大问题的小版本。
3. 开辟一个dp列表用来实现状态转移方程
4. res最开始为列表的第一个元素，如果列表只有一个元素，返回就是了
5. 以[1,-2,3,10,-4,7,2,-5]为例：dp[2] = max(array[1], dp[1]+array[1])
6. 解读：dp[1] = max(array[0], dp[0]+array[0]) = 1
7. dp[2] = max(array[1], dp[1]+array[1]) -》 dp[2] = max(-2, -1) = -1
8. 对于dp[3]来说，max(3, 3-1)肯定选3
9. 对于dp[4]来说，max(10, 10 +13)肯定选13
10. dp的值：[0, 1, -1, 3, 13, 9, 16, 18, 13]
11. dp数组是游离于array数组之外，他只是用来记录子数组的值累加的过程中能够取得的最大值

12.想不明白的点刷了个抖音想明白了。。为什么这样一个状态转移方程，就能够取出某一部分的子数组来而不是连续的呢？[1,-2,3,10,-4,7,2,-5]，为什么从3开始的子数组，1和-2呢？原因就在这一句：max(array[i-1], dp[i-1]+array[i-1])，如果是连续的子数组那么会取到这个dp[i-1]+array[i-1]，否则选用array[i-1]就斩断了，比如到3的时候，dp+array还不如array大，那么就从这个地方砍断，以array为起始继续往后面走！

13. 感觉这个说到底还是和dp的无后效性有关，“未来与过去无关”、“过去不影响未来”，dp[i]只会关心dp[i-1]，至于dp[i-2]、dp[i-3].。。。who care？

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