Python实现最大子序和的方法示例

描述给定一个序列（至少含有1个数），从该序列中寻找一个连续的子序列，使得子序列的

描述

给定一个序列（至少含有 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

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持脚本之家。

Python 最大子序和