53. Maximum Subarray

1,216次阅读
没有评论
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

<strong>Input:</strong> [-2,1,-3,4,-1,2,1,-5,4],
<strong>Output:</strong> 6
<strong>Explanation:</strong> [4,-1,2,1] has the largest sum = 6.

解法:

class Solution:
    def maxSubArray(self, nums: 'List[int]') -> 'int':
        if not nums:
            return 0

        curSum = maxSum = nums[0]
        for num in nums[1:]:
            curSum = max(num, curSum + num)
            maxSum = max(maxSum, curSum)

        return maxSum

说明:

cursum是计算累加的数值和 与当前的数值大小之间的最大值,如果过去遍历的数据的累加和都没有现在的值大,那么过去累加的数据都没有任何的意义

maxsum就是不断的计算cursum的最大值,返回最终的结果

admin
版权声明:本站原创文章,由admin2019-02-17发表,共计487字。
转载提示:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)