DP-leetcode-最大子序和(dp和分治法)

题目：

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

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

思路：

连续子数据就是一个开始和结尾的区间，可以把当前元素作为区间的结尾来判断的话

以 i 结尾的所有子数组中，和最大的是多少？

? 有两种状态：

? 当前位置的值自己组成一个数组

? i位置的值 + i-1结尾的所有子数组的最大和 = dp[i] + dp[i-1]

? 下一步是获取最大值，max（dp[i] + dp[i-1]， dp[i]）

解题：

def maxSubArray(self, nums):
    if not nums:
        return 0
    res =  nums[0] #记录最大值
    for i in range(1,len(nums)):
        nums[i] = max(nums[i-1]+nums[i], nums[i])
        res = max(nums[i], res)
        return res

进阶:

分治法求解:

DP-leetcode-最大子序和(dp和分治法)

原文：https://www.cnblogs.com/hornets/p/12787912.html