給定一個整數(shù)數(shù)組 nums ，找到一個具有大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其大和。

在茅箭等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強發(fā)展的系統(tǒng)性、市場前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務理念，為客戶提供成都網(wǎng)站設計、成都網(wǎng)站制作 網(wǎng)站設計制作定制網(wǎng)站,公司網(wǎng)站建設,企業(yè)網(wǎng)站建設,成都品牌網(wǎng)站建設,網(wǎng)絡營銷推廣,成都外貿(mào)網(wǎng)站制作,茅箭網(wǎng)站建設費用合理。

示例:

輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和大，為 6。

進階:

如果你已經(jīng)實現(xiàn)復雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。

思路：

首先我們分析題目，我們思考，為什么大和的連續(xù)子數(shù)組不包含其他的元素而是這幾個呢？因為如果我們想在現(xiàn)有的基礎上去擴展當前連續(xù)子數(shù)組，相鄰的元素是一定要被加入的，而相鄰元素中可能會減損當前的和。

思路一：

遍歷法，On:

算法過程：遍歷數(shù)組，用onesum去維護當前元素加起來的和。當onesum出現(xiàn)小于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)
      #出現(xiàn)onesum<0的情況，就設為0，重新累積和
      if onesum < 0:
        onesum = 0
    return maxsum

本文題目：python實現(xiàn)最大子序和（分治+動態(tài)規(guī)劃）-創(chuàng)新互聯(lián)
當前路徑：http://www.chinadenli.net/article30/dhohso.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供移動網(wǎng)站建設、網(wǎng)站制作、搜索引擎優(yōu)化、微信小程序、外貿(mào)建站、云服務器

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)