題目描述：
一個有 n 個元素的數組，這 n 個元素既可以是正數也可以是負數，數組中連續的一個或多個元素可以組成一個連續的子數組，一個數組可能有多個這種連續的子數組，求子數組的最大值。例如，對于數組 [1，-2，4，8，-4，7，-1，-5] 而言，其最大和的子數組為 [4,8,-4,7]，最大值為 15。
方法：
1.蠻力法
找出所有的子數組，然后求出子數組的和，在所有子數組的和中取最大值。
代碼實現：
#!/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('參數不合理！')
return
thisSum = 0
maxSum = 0
i = 0
while i < len(arr):
j = i
while j < len(arr):# j 控制連續子數組包含的元素個數
thisSum = 0
k = i # k 表示連續子數組開始的下標
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))
結果：
算法性能分析：
這種方法的時間復雜度為O(n3)；
2.重復利用已經計算的子數組和
由于 sum[i，j] = sum[i，j-1] + arr[j]，在計算 sum[i，j] 的時候可以使用前面已計算出的 sum[i，j-1] 而不需要重新計算，采用這種方法可以省去計算 sum[i，j-1] 的時間，從而提高效率。
代碼實現：
#!/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('參數不合理！')
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 重復利用
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))
結果：
算法性能分析：
使用了雙重循環，時間復雜度為O(n2)；
3.動態規劃
首先可以根據數組最后一個元素 arr[n-1] 與最大子數組的關系分為以下三種情況討論：
(包含或不包含，包含的話肯定以最后一個元素結尾；不包含的話，或者最后一個元素單獨構成最大子數組，或者轉換為求 arr[1…n-2] 的最大子數組)
(1) 最大子數組包含 arr[n-1]，即最大子數組以 arr[n-1] 結尾；
(2) arr[n-1] 單獨構成最大子數組；
(3) 最大子數組不包含 arr[n-1]，那么求 arr[1…n-1] 的最大子數組可以轉換為求 arr[1…n-2] 的最大子數組。
所以有：
代碼實現：
#!/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('參數不合理！')
return
n = len(arr)
End = [None] * n # End[i] 表示包含 arr[i] 的最大子數組和
All = [None] * n # All[i] 表示最大子數組和
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))
結果：
算法性能分析：
時間復雜度為O(n)；
由于額外申請了兩個數組，所以空間復雜度為O(n)；
4.優化的動態規劃
方法3中每次其實只用到了 End[i-1] 與 All[i-1] ，而不是整個數組中的值，所以可以定義兩個變量來保存 End[i-1] 與 All[i-1] 的值，并且可以反復利用。
代碼實現：
#!/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('參數不合理！')
return
nAll = arr[0] # 最大子數組和
nEnd = arr[0] # 包含最后一個元素的最大子數組和
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))
結果：
算法性能分析：
時間復雜度為O(n)；
空間復雜度為O(1)；
引申：
在知道了子數組的最大值后，如何確定最大子數組的和？
思路：
代碼實現：
#!/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 # 記錄最大子數組起始位置
self.end = 0 # 記錄最大子數組結束位置
def maxSubArrSum(self, arr):
n = len(arr)
maxSum = -2 ** 31 # 子數組最大值
nSum = 0 # 包含子數組最后一位的最大值
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('連續最大和為:', t.maxSubArrSum(arr))
print('begin at ', t.getBegin())
print('end at ', t.getEnd())
結果：
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
