温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

怎么使用Python实现最大子序和

发布时间:2021-04-07 09:56:52 来源:亿速云 阅读:213 作者:小新 栏目:开发技术

这篇文章将为大家详细讲解有关怎么使用Python实现最大子序和,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。

描述

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

测试结果如下:

怎么使用Python实现最大子序和 

本地运行时间为14.7s,说明我的方法太粗暴了。应该寻找更好的算法。

怎么使用Python实现最大子序和 

我 优化后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!!!!!!!!!!!!!!!这也太强了吧!!

怎么使用Python实现最大子序和 

优化后,运行时间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实现最大子序和”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,使各位可以学到更多知识,如果觉得文章不错,请把它分享出去让更多的人看到。

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI