這篇文章將為大家詳細講解有關怎么使用Python實現(xiàn)大子序和，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

在嘉定等地區(qū)，都構建了全面的區(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)站建設費用合理。

描述

給定一個序列（至少含有 1 個數(shù)），從該序列中尋找一個連續(xù)的子序列，使得子序列的和大。
例如，給定序列 [-2,1,-3,4,-1,2,1,-5,4]，
連續(xù)子序列 [4,-1,2,1] 的和大，為 6。

我 v1.0

class Solution:
  def maxSubArray(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    l = len(nums)
    i = 0
    result = nums[0]
    while i < l:
      sums = []
      temp = 0
      for j in range(i, l):
        temp+=nums[j]
        sums.append(temp)
      if result < max(sums):
        result = max(sums)
      i+=1
    return result

測試結果如下：

 

本地運行時間為14.7s，說明我的方法太粗暴了。應該尋找更好的算法。

 

我 優(yōu)化后v1.1。優(yōu)化方案，去掉sums數(shù)組，節(jié)省空間。但時間復雜度仍然不變。

  l = len(nums)
    i = 0
    result = nums[0]
    while i < l:
      temp = 0
      for j in range(i, l):
        temp+=nums[j]
        if result < temp:
          result = temp
      i+=1
    return result

仍然只通過200/202測試用例，仍然超出時間限制。但本地運行時間為8.3s。有進步。

別人，分治法。時間復雜度O(NlogN)

將輸入的序列分成兩部分，這個時候有三種情況。
1）大子序列在左半部分
2）大子序列在右半部分
3）大子序列跨越左右部分。

前兩種情況通過遞歸求解，第三種情況可以通過。

分治法代碼大概如下，emmm。。。目前還沒有完全理解。

def maxC2(ls,low,upp): 
  #"divide and conquer" 
  if ls is None: return 0 
  elif low==upp: return ls[low] 

  mid=(low+upp)/2 #notice: in the higher version python, “/” would get the real value 
  lmax,rmax,tmp,i=0,0,0,mid 
  while i>=low: 
    tmp+=ls[i] 
    if tmp>lmax: 
      lmax=tmp 
    i-=1 
  tmp=0 
  for k in range(mid+1,upp): 
    tmp+=ls[k] 
    if tmp>rmax: 
      rmax=tmp 
  return max3(rmax+lmax,maxC2(ls,low,mid),maxC2(ls,mid+1,upp)) 

def max3(x,y,z): 
  if x>=y and x>=z: 
    return x 
  return max3(y,z,x)

動態(tài)規(guī)劃算法，時間復雜度為O(n)。
分析：尋找最優(yōu)子結構。

   l = len(nums)
    i = 0
    sum = 0
    MaxSum = nums[0]
    while i < l:
      sum+=nums[i]
      if sum > MaxSum:
          MaxSum = sum
      if sum < 0:
        sum = 0
      i+=1
    return MaxSum

Oh！My god?。。??。。。。。。。∵\行只花了0.2s?。。。。。。。。。。。。。。∵@也太強了吧??！

 

優(yōu)化后,運行時間0.1s.

 sum = 0
    MaxSum = nums[0]
    for i in range(len(nums)):
      sum += nums[i]
      if sum > MaxSum:
        MaxSum = sum
      if sum < 0:
        sum = 0
    return MaxSum

其中

sum += nums[i]必須緊挨。

MaxSum = sum

關于“怎么使用Python實現(xiàn)大子序和”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。

新聞標題：怎么使用Python實現(xiàn)最大子序和-創(chuàng)新互聯(lián)
分享鏈接：http://weahome.cn/article/dhcjdi.html