動态規劃系列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)