LeetCode刷题笔记:字节跳动-动态或贪心(3)-最大子序和

4.最大子序和

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例一:

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

本题思路为遍历数组,设定一个值sm记录截止到当前值的子数组之和,设定一个mx值记录最大值。若子数组和小于0,则置sm为当前值。若子数组和大于0,更新mx为mx和sm+当前值之间的最大值,代码如下:

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        mx = nums[0]
        sm = nums[0]
        for i in range(1,len(nums)):
            if sm<0:
                sm = nums[i]
            else:
                sm += nums[i]
            mx = max(mx,sm)
        return mx

点赞

发表评论

[2;3Rer>