动态规划系列1.最大子序和python

文章目录

• 题目
• 题解

题目

最大子序和

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

示例：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]

输出：6

题解

def maxSubArray(nums):
        max_v = nums[0]
        sub_sum = 0
        for num in nums:
            sub_sum += num
            if sub_sum < num:
                sub_sum = num 
            if sub_sum > max_v:
                max_v = sub_sum
        return max_v
           

这个题与剑指offer中的[42.连续子数组的最大和]是同一道题目(https://blog.csdn.net/weixin_41651734/article/details/115487848)