快捷導(dǎo)航

python如何求數(shù)組連續(xù)最大和的示例代碼

更新時間：2020年02月04日 11:33:01 作者：布歐不歐

這篇文章主要介紹了python如何求數(shù)組連續(xù)最大和的示例代碼，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

題目描述：

一個有 n 個元素的數(shù)組，這 n 個元素既可以是正數(shù)也可以是負數(shù)，數(shù)組中連續(xù)的一個或多個元素可以組成一個連續(xù)的子數(shù)組，一個數(shù)組可能有多個這種連續(xù)的子數(shù)組，求子數(shù)組的最大值。例如，對于數(shù)組 [1，-2，4，8，-4，7，-1，-5] 而言，其最大和的子數(shù)組為 [4,8,-4,7]，最大值為 15。

方法：

蠻力法
重復(fù)利用已經(jīng)計算的子數(shù)組和
動態(tài)規(guī)劃
優(yōu)化的動態(tài)規(guī)劃

1.蠻力法

找出所有的子數(shù)組，然后求出子數(shù)組的和，在所有子數(shù)組的和中取最大值。

代碼實現(xiàn)：

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @Time  : 2020/1/29 21:59
# @Author : buu
# @Software: PyCharm
# @Blog  ：https://blog.csdn.net/weixin_44321080
def maxSubArrSum(arr):
  if arr == None or len(arr) <= 0:
    print('參數(shù)不合理！')
    return
  thisSum = 0
  maxSum = 0
  i = 0
  while i < len(arr):
    j = i
    while j < len(arr):# j 控制連續(xù)子數(shù)組包含的元素個數(shù)
      thisSum = 0
      k = i # k 表示連續(xù)子數(shù)組開始的下標
      while k < j:
        thisSum += arr[k]
        k += 1
      if thisSum > maxSum:
        maxSum = thisSum
      j += 1
    i += 1
  return maxSum


if __name__ == '__main__':
  arr = [1, -2, 4, 8, -4, 7, -1, -5]
  print('1 max sub array sum:', maxSubArrSum(arr))

結(jié)果：

算法性能分析：
這種方法的時間復(fù)雜度為O(n3)；

2.重復(fù)利用已經(jīng)計算的子數(shù)組和

由于 sum[i，j] = sum[i，j-1] + arr[j]，在計算 sum[i，j] 的時候可以使用前面已計算出的 sum[i，j-1] 而不需要重新計算，采用這種方法可以省去計算 sum[i，j-1] 的時間，從而提高效率。

代碼實現(xiàn)：

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @Time  : 2020/1/30 10:53
# @Author : buu
# @Software: PyCharm
# @Blog  ：https://blog.csdn.net/weixin_44321080
def maxSubArrSum(arr):
  if arr == None or len(arr) <= 0:
    print('參數(shù)不合理！')
    return
  maxSum = -2 ** 31
  i = 0
  while i < len(arr): # i: 0~7
    sums = 0
    j = i
    while j < len(arr): # j: 0~7
      sums += arr[j] # sums 重復(fù)利用
      if sums > maxSum: # 每加一次就判斷一次
        maxSum = sums
      j += 1
    i += 1
  return maxSum


if __name__ == '__main__':
  arr = [1, -2, 4, 8, -4, 7, -1, -5]
  print('2 max sub array sum:', maxSubArrSum(arr))

結(jié)果：

算法性能分析：
使用了雙重循環(huán)，時間復(fù)雜度為O(n2)；

3.動態(tài)規(guī)劃

首先可以根據(jù)數(shù)組最后一個元素 arr[n-1] 與最大子數(shù)組的關(guān)系分為以下三種情況討論：
(包含或不包含，包含的話肯定以最后一個元素結(jié)尾；不包含的話，或者最后一個元素單獨構(gòu)成最大子數(shù)組，或者轉(zhuǎn)換為求 arr[1…n-2] 的最大子數(shù)組)
(1) 最大子數(shù)組包含 arr[n-1]，即最大子數(shù)組以 arr[n-1] 結(jié)尾；
(2) arr[n-1] 單獨構(gòu)成最大子數(shù)組；
(3) 最大子數(shù)組不包含 arr[n-1]，那么求 arr[1…n-1] 的最大子數(shù)組可以轉(zhuǎn)換為求 arr[1…n-2] 的最大子數(shù)組。
所以有：

代碼實現(xiàn)：

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @Time  : 2020/1/30 11:19
# @Author : buu
# @Software: PyCharm
# @Blog  ：https://blog.csdn.net/weixin_44321080
def maxSubArrSum(arr):
  if arr == None or len(arr) <= 0:
    print('參數(shù)不合理！')
    return
  n = len(arr)
  End = [None] * n # End[i] 表示包含 arr[i] 的最大子數(shù)組和
  All = [None] * n # All[i] 表示最大子數(shù)組和
  End[n - 1] = arr[n - 1]
  All[n - 1] = arr[n - 1]
  End[0] = All[0] = arr[0]
  i = 1
  while i < n:
    End[i] = max(End[i - 1] + arr[i], arr[i]) # i=1時若arr[0]<0,則從arr[1]重新開始
    All[i] = max(End[i], All[i - 1])
    i += 1
  return All[n - 1]


if __name__ == '__main__':
  arr = [1, -2, 4, 8, -4, 7, -1, -5]
  print('3 max sub array sum:', maxSubArrSum(arr))

結(jié)果：

算法性能分析：
時間復(fù)雜度為O(n)；
由于額外申請了兩個數(shù)組，所以空間復(fù)雜度為O(n)；

4.優(yōu)化的動態(tài)規(guī)劃

方法3中每次其實只用到了 End[i-1] 與 All[i-1] ，而不是整個數(shù)組中的值，所以可以定義兩個變量來保存 End[i-1] 與 All[i-1] 的值，并且可以反復(fù)利用。

代碼實現(xiàn)：

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @Time  : 2020/1/30 11:55
# @Author : buu
# @Software: PyCharm
# @Blog  ：https://blog.csdn.net/weixin_44321080
def maxSubArrSum(arr):
  if arr == None or len(arr) <= 0:
    print('參數(shù)不合理！')
    return
  nAll = arr[0] # 最大子數(shù)組和
  nEnd = arr[0] # 包含最后一個元素的最大子數(shù)組和
  i = 1
  while i < len(arr):
    nEnd = max(nEnd + arr[i], arr[i])
    nAll = max(nEnd, nAll)
    i += 1
  return nAll


if __name__ == '__main__':
  arr = [1, -2, 4, 8, -4, 7, -1, -5]
  print('4 max sub array sum:', maxSubArrSum(arr))

結(jié)果：

算法性能分析：
時間復(fù)雜度為O(n)；
空間復(fù)雜度為O(1)；

引申：

在知道了子數(shù)組的最大值后，如何確定最大子數(shù)組的和？

思路：

代碼實現(xiàn)：

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @Time  : 2020/1/30 12:01
# @Author : buu
# @Software: PyCharm
# @Blog  ：https://blog.csdn.net/weixin_44321080
class Test:
  def __init__(self):
    self.begin = 0 # 記錄最大子數(shù)組起始位置
    self.end = 0 # 記錄最大子數(shù)組結(jié)束位置

  def maxSubArrSum(self, arr):
    n = len(arr)
    maxSum = -2 ** 31 # 子數(shù)組最大值
    nSum = 0 # 包含子數(shù)組最后一位的最大值
    nStart = 0
    i = 0
    while i < n:
      if nSum < 0:
        nSum = arr[i]
        nStart = i
      else:
        nSum += arr[i]
      if nSum > maxSum:
        maxSum = nSum
        self.begin = nStart
        self.end = i
      i += 1
    return maxSum

  def getBegin(self):
    return self.begin

  def getEnd(self):
    return self.end


if __name__ == '__main__':
  arr = [1, -2, 4, 8, -4, 7, -1, -5]
  t = Test()
  print('連續(xù)最大和為:', t.maxSubArrSum(arr))
  print('begin at ', t.getBegin())
  print('end at ', t.getEnd())

結(jié)果：