Leetcode 动态规划——最大子序和

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

示例:

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

遍历

def bianli_maxSubArray(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    max_num,sum_num=0,0
    for i in range(len(nums)):
        sum_num +=nums[i] #累加
        if sum_num > max_num:
            max_num = sum_num #取代更新
        elif sum_num<0:
            sum_num=0
    print(max_num)

动态规划

def dp_maxSubArray(nums):
    '''
    :param nums:
    :return:
    '''
    for i in range(1, len(nums)):
        sub_max = max(nums[i - 1] + nums[i], nums[i]) #局部最大
        nums[i] = sub_max #直接更新节点 保留上一次
    print(max(nums))