描述
給定一個序列（至少含有 1 個數），從該序列中尋找一個連續的子序列，使得子序列的和最大。
例如，給定序列 [-2,1,-3,4,-1,2,1,-5,4]，
連續子序列 [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，說明我的方法太粗暴了。應該尋找更好的算法。
?
我 優化后v1.1。優化方案，去掉sums數組，節省空間。但時間復雜度仍然不變。
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)
動態規劃算法，時間復雜度為O(n)。
分析：尋找最優子結構。
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！?。。。。。。。。。。。。?！這也太強了吧?。?
?
優化后,運行時間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
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
