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

 更新时间:2019年07月05日 10:01:41   作者:神不烦   我要评论
这篇文章主要介绍了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

测试结果如下:

 

本地运行时间为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 将RGB图像转换为Pytho灰度图像的实例

    Python 将RGB图像转换为Pytho灰度图像的实例

    下面小编就为大家带来一篇Python 将RGB图像转换为Pytho灰度图像的实例。具有很好的参考价值。希望对大家有所帮助。一起跟随小编过来看看吧
    2017-11-11
  • Python对CSV、Excel、txt、dat文件的处理

    Python对CSV、Excel、txt、dat文件的处理

    本文介绍的是Python对CSV、Excel、txt、dat文件的处理,具有一定的参考价值,需要的朋友跟随小编一起来看下
    2018-09-09
  • Python面向对象之类的封装操作示例

    Python面向对象之类的封装操作示例

    这篇文章主要介绍了Python面向对象之类的封装操作,结合具体实例形式分析了Python面向对象程序设计中类方法的定义与使用相关操作技巧,需要的朋友可以参考下
    2019-06-06
  • 关于Python内存分配时的小秘密分享

    关于Python内存分配时的小秘密分享

    这篇文章主要给大家分享介绍了关于Python内存分配时的小秘密,文中通过示例代码介绍的非常详细,对大家学习或者使用Python具有一定的参考学习价值,需要的朋友们下面来一起学习学习吧
    2019-09-09
  • python实现抽奖小程序

    python实现抽奖小程序

    这篇文章主要为大家详细介绍了python实现抽奖小程序,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
    2019-05-05
  • python队列Queue的详解

    python队列Queue的详解

    这篇文章主要介绍了python队列Queue,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
    2019-05-05
  • Python闭包实现计数器的方法

    Python闭包实现计数器的方法

    这篇文章主要介绍了Python闭包实现计数器的方法,分析了闭包的概念及实现计数器的相关技巧,需要的朋友可以参考下
    2015-05-05
  • Django实现单用户登录的方法示例

    Django实现单用户登录的方法示例

    这篇文章主要介绍了Django实现单用户登录的方法示例,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
    2019-03-03
  • python爬取网站数据保存使用的方法

    python爬取网站数据保存使用的方法

    这篇文章主要介绍了使用Python从网上爬取特定属性数据保存的方法,其中解决了编码问题和如何使用正则匹配数据的方法,详情看下文
    2013-11-11
  • python通过get,post方式发送http请求和接收http响应的方法

    python通过get,post方式发送http请求和接收http响应的方法

    这篇文章主要介绍了python通过get,post方式发送http请求和接收http响应的方法,涉及Python使用urllib模块与urllib2模块实现get与post发送数据的相关技巧,需要的朋友可以参考下
    2015-05-05

最新评论