剑指offer(python)_动态规划——55. 连续子数组的最大和

55.（简单）——动态规划

输入一个 非空 整型数组，数组里的数可能为正，也可能为负。

数组中一个或连续的多个整数组成一个子数组。

求所有子数组的和的最大值。

要求时间复杂度为O(n)。

样例

输入：[1, -2, 3, 10, -4, 7, 2, -5]

输出：18

解题思路：

动态规划问题 

状态：dp[i]记录当前以i结尾的连续数组的最大值

（1）如果 dp[i]= dp[i-1]+nums[i] 比 num[i] 则dp[i] 小，就不是连续数组的最大值，另起炉灶，dp[i]=nums[i],状态从【i】重新开始，并把这个状态记录下来

（2）如果 dp[i]= dp[i-1]+nums[i] 比 num[i] 则dp[i] 小，是连续数组的最大值，把这个状态记录下来

（3）考虑特殊情况，比如数组为空或者为1

参考代码：

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        size = len(nums)
        dp = [False for _ in range(size)]#记录状态：当前以i结尾的最大值记录在里面
        if size==0 :#特殊1
            return None
        if size==1: #特殊2
            return nums[0]
        dp[0] =nums[0] 
        #核心代码
        for i in range(1,size):
            dp[i] = max(dp[i-1]+nums[i],nums[i])#记录最大状态
        return max(dp)