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

2019-11-25 12:30:52

字体：大中小

来源：转载

供稿：网友

描述

给定一个序列（至少含有 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]必须紧挨。