• 为了保证你在浏览本网站时有着更好的体验,建议使用类似Chrome、Firefox之类的浏览器~~
    • 如果你喜欢本站的内容何不Ctrl+D收藏一下呢,与大家一起分享各种编程知识~
    • 本网站研究机器学习、计算机视觉、模式识别~当然不局限于此,生命在于折腾,何不年轻时多折腾一下

53. Maximum Subarray

leetcode admin 1个月前 (02-17) 76次浏览 0个评论 扫描二维码
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [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 的最大值,返回最终的结果


Deeplearn, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明53. Maximum Subarray
喜欢 (0)
admin
关于作者:

您必须 登录 才能发表评论!