Python算法與數據結構--求所有子數組的和的最大值

玄魂工作室秘書 玄魂工作室 昨天

題目：輸入一個整形數組，數組里有正數也有負數。數組中連續的一個或多個整數組成一個子數組，每個子數組都有一個和。

求所有子數組的和的最大值。要求時間復雜度為O(n)。

這個題目有多個解法，比如可以用一個二維數組存之前每個數據的和，然后在進行大小比較；但是這樣時間負責度就是O(n2)了。

換個思路思考下，因為是要最大數，那么就不需要存儲，只需要找最大值就可以了。但是為了找子序列的最大和，在遇到相加為負數的情況要跳過，這塊注意代碼中最后一個if的注釋。

基本思路：一個數一個數相加，相加后和最大數以及當前這個數對比，找出最大的；如果相加后是負數，則累加清零

代碼-----------

# -*- coding: utf-8 -*-

"""

題目：輸入一個整形數組，數組里有正數也有負數。

數組中連續的一個或多個整數組成一個子數組，每個子數組都有一個和。

求所有子數組的和的最大值。要求時間復雜度為O(n)。

基本思路：一個數一個數相加，相加后和最大數以及當前這個數對比，找出最大的；如果相加后是負數，則累加清零

"""

if __name__ == "__main__":

#初始化數組，測試數據

#dataList = [-3,-10,30,-5,-6,-100,300]

#dataList = [-3,-10,-30,-5,-6,-1,-100,-300]

#dataList = [-3,-10,0,-5,-6,-100,-300]

dataList = [3,10,0,5,6,100,300]

#dataList = [0,0,0,0,0,0,0]

#prd_data用來記錄前面累加的數，一旦累加值是負數，則清零

pre_data = dataList[0]

#用來記錄最大值

max_data = pre_data

#遍歷數據組進行累加和大小對比

for i in range(len(dataList)):

currData = dataList[i]

#第一個數用來做初始化，從第二個數開始算

if i==0:

continue

else:

#相加后進行temp_data，max_data以及currData的大小對比，找出最大的

temp_data = currData + pre_data

if temp_data > currData:

if temp_data > max_data:

max_data = temp_data

else:

if currData > max_data:

max_data = currData

#如果相加后是負數，則清0，因為一旦出現負數在相加只會讓最大值變小

#這塊注意**********一定是相加后是負數，而不是這個數本身是負數***********

#因為本身是負數，但是相加后是正數，對后面的數據增大還是有幫助的

if temp_data > 0:

pre_data = temp_data

else:

pre_data = 0

print max_data

歡迎關注玄魂工作室垂直訂閱號 “白話算法”。

優質算法課程推薦，掃碼了解詳情：

總結

以上是生活随笔為你收集整理的python求数组最大值_Python算法与数据结构--求所有子数组的和的最大值的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。