资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

python实现最大子序和(分治+动态规划)-创新互联

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

在茅箭等地区,都构建了全面的区域性战略布局,加强发展的系统性、市场前瞻性、产品创新能力,以专注、极致的服务理念,为客户提供成都网站设计、成都网站制作 网站设计制作定制网站,公司网站建设,企业网站建设,成都品牌网站建设,网络营销推广,成都外贸网站制作,茅箭网站建设费用合理。

示例:

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

进阶:

如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。

思路:

首先我们分析题目,我们思考,为什么大和的连续子数组不包含其他的元素而是这几个呢?因为如果我们想在现有的基础上去扩展当前连续子数组,相邻的元素是一定要被加入的,而相邻元素中可能会减损当前的和。

思路一:

遍历法,On:

算法过程:遍历数组,用onesum去维护当前元素加起来的和。当onesum出现小于0的情况时,我们把它设为0。然后每次都更新全局大值。

class Solution:
  def maxSubArray(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    #onesum维护当前的和
    onesum = 0
    maxsum = nums[0]
    for i in range(len(nums)):
      onesum += nums[i]
      maxsum = max(maxsum, onesum)
      #出现onesum<0的情况,就设为0,重新累积和
      if onesum < 0:
        onesum = 0
    return maxsum

分享题目:python实现最大子序和(分治+动态规划)-创新互联
网页URL:http://www.cdkjz.cn/article/dhohso.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220