求最大連續子序列的和是一個很經典很古老的面試題了，本文我們就和大家分享關於用Python語言描述最大連續子序列和方法，希望能幫助到大家。
1.問題描述
假設有一數組（python裡為list啦）[1,3,-3,4,-6,-1]，求數組中最大連續子序列的和。例如在此數組中，最大連續子序列的和為5，即1+3+（-3）+4 = 5
2.O(n2)的解法
最簡單粗暴的方式，雙層循環，用一個maxsum標識最大連續子序列和。然後每次判斷更新。沒有太多可以說的，直接上程式碼
def maxSum(list):
maxsum = list[0]
for i in range(len(list)):
maxtmp = 0
for j in range(i,len(list)):
maxtmp += list[j]
if maxtmp > maxsum:
maxsum = maxtmp
return maxsum
if __name__ == '__main__':
list = [1,3,-3,4,-6]
maxsum = maxSum(list)
print "maxsum is",maxsum#運行結果
##
maxsum is 5
def maxSum(list_of_nums):
maxsum = 0
maxtmp = 0
for i in range(len(list_of_nums)):
if maxtmp <= 0:
maxtmp = list_of_nums[i]
else:
maxtmp += list_of_nums[i]
if(maxtmp > maxsum):
maxsum = maxtmp
return maxsum
if __name__ == '__main__':
list_of_num = [1,3,-3,4,-6]
maxsum = maxSum(list_of_num)
print "maxsum is: ",maxsummaxsum is 5
以上是用Python語言描述最大連續子序列和的詳細內容。更多資訊請關注PHP中文網其他相關文章！
