53.最大子序和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

def maxSubArray(nums):
    """
    动态规划：分解成小问题，先解决小问题，当小问题解决完，即大问题也就解决了（先解后合发展一组解）
    返回数组中具有最大和的连续子数组的和
    动态规划算法的核心就是记住已经解决过的子问题的解
    :param nums: List[int]
    :return: int
    """
    for i in range(1, len(nums)):
        #理解：假设我是一个数字，我需要联合前面一个数变强，如果前面一个是负数，那么对我没有加强作用，我还不如自己一个人
        #如果是一个正数，那么对我有增益效果，就加上前一个数（前一个数也是这样来的，这样就满足了连续子数组最大和，
        # 相当于前面一个人加强自己的过程已经完成，这就是一个小过程）变成全新的我，最后返回队伍中的最强大的（大过程，最终结果）
        nums[i] = nums[i] + max(nums[i - 1], 0)
    return max(nums)

print(maxSubArray([5, 4, -1, 7, 8]))

官方解答：leetcode官方

复习动态规划：CSDN动态规划

动态规划（自底向上，先解后合，发展一组解）算法的核心就是记住已经解决过的子问题的解

①最优子结构

用动态规划求解最优化问题的第一步就是刻画最优解的结构，如果一个问题的解结构包含其子问题的最优解，就称此问题具有最优子结构性质。因此，某个问题是否适合应用动态规划算法，它是否具有最优子结构性质是一个很好的线索。使用动态规划算法时，用子问题的最优解来构造原问题的最优解。因此必须考查最优解中用到的所有子问题。

②重叠子问题

在斐波拉契数列和钢条切割结构图中，可以看到大量的重叠子问题，比如说在求fib（6）的时候，fib（2）被调用了5次，在求cut（4）的时候cut（0）被调用了4次。如果使用递归算法的时候会反复的求解相同的子问题，不停的调用函数，而不是生成新的子问题。如果递归算法反复求解相同的子问题，就称为具有重叠子问题（overlapping subproblems）性质。在动态规划算法中使用数组来保存子问题的解，这样子问题多次求解的时候可以直接查表不用调用函数递归。