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

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

赞 (0)

相关推荐

  • Python语言描述最大连续子序列和

    求最大连续子序列的和是一个很经典很古老的面试题了,记得在刚毕业找工作面试那会也遇到过同款问题.今儿突然想起来,正好快到毕业季,又该是苦逼的应届生们各种面试的时候到了,就给写了一些小代码解决这个问题.也希望各位找工作的同志们都拿到心目中理想的offer,从此以后,战胜高富帅,赢取白富美,走上人生巅峰. 1.问题描述 假设有一数组(python里为list啦)[1,3,-3,4,-6,-1],求数组中最大连续子序列的和.例如在此数组中,最大连续子序列的和为5,即1+3+(-3)+4 = 5 2.O(

  • 详解Python最长公共子串和最长公共子序列的实现

    详解Python最长公共子串和最长公共子序列的实现

    最长公共子串(The Longest Common Substring) LCS问题就是求两个字符串最长公共子串的问题.解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0.然后求出对角线最长的1的序列,其对应的位置就是最长匹配子串的位置. def find_lcsubstr(s1, s2): m=[[0 for i in range(len(s2)+1)] for j in range(len(s1)+1)] #生成0矩阵,为方便后续计算,比字符串长度

  • 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 res

  • Python实现检测文件MD5值的方法示例

    本文实例讲述了Python实现检测文件MD5值的方法.分享给大家供大家参考,具体如下: 前面介绍过Python计算文件md5值的方法,这里分析一下Python检测文件MD5值的另一种实现方法. 概述: MD5(单向散列算法)的全称是Message-Digest Algorithm 5(信息-摘要算法),经MD2.MD3和MD4发展而来.MD5算法的使用不需要支付任何版权费用. 实现代码: #python 检测文件MD5值 #python version 2.6 import hashlib im

  • Python简单计算文件MD5值的方法示例

    本文实例讲述了Python简单计算文件MD5值的方法.分享给大家供大家参考,具体如下: 一 代码 import sys import hashlib import os.path filename = sys.argv[1] if os.path.isfile(filename): fp=open(filename,'rb') contents=fp.read() fp.close() print(hashlib.md5(contents).hexdigest()) else: print('f

  • 纯python进行矩阵的相乘运算的方法示例

    本文介绍了纯python进行矩阵的相乘运算的方法示例,分享给大家,具体如下: def matrixMultiply(A, B): # 获取A的行数和列数 A_row, A_col = shape(A) # 获取B的行数和列数 B_row, B_col = shape(B) # 不能运算情况的判断 if(A_col != B_row): raise ValueError # 最终的矩阵 result = [] # zip 解包后是转置后的元组,强转成list, 存入result中 BT = [li

  • python库skimage给灰度图像染色的方法示例

    灰度图像染成红色和黄色 # 1.将灰度图像转换为RGB图像 image = color.gray2rgb(grayscale_image) # 2.保留红色分量和黄色分量 red_multiplier = [1, 0, 0] yellow_multiplier = [1, 1, 0] # 3.显示图像 fig, (ax1, ax2) = plt.subplots(ncols=2, figsize=(8, 4), sharex=True, sharey=True) ax1.imshow(red_m

  • python使用selenium爬虫知乎的方法示例

    说起爬虫一般想到的情况是,使用 python 中都通过 requests 库获取网页内容,然后通过 beautifulSoup 进行筛选文档中的标签和内容.但是这样有个问题就是,容易被反扒机制所拦住. 反扒机制有很多种,例如知乎:刚开始只加载几个问题,当你往下滚动时才会继续往下面加载,而且在往下滚动一段距离时就会出来一个登陆的弹框. 这样的机制对于通过获取服务器返回内容的爬虫方式进行了限制,我们只能获得前几个回答,而没办法或许后面的回答. 所以需要使用 selenium 模拟真实浏览器进行操作.

  • Python统计列表元素出现次数的方法示例

    1. 引言 在使用Python的时候,通常会出现如下场景: array = [1, 2, 3, 3, 2, 1, 0, 2] 获取array中元素的出现次数 比如,上述列表中:0出现了1次,1出现了2次,2出现了3次,3出现了2次. 本文阐述了Python获取元素出现次数的几种方法.点击获取完整代码. 2. 方法 获取元素出现次数的方法较多,这里我提出如下5个方法,谨供参考.下面的代码,传入的参数均为 array = [1, 2, 3, 3, 2, 1, 0, 2] 2.1 Counter方法

  • Python脚本读取Consul配置信息的方法示例

    Python脚本读取Consul配置信息的方法示例

    先来说一下背景,为什么要写脚本去读Consul的配置信息呢?Consul是啥呢?consul是google开源的一个使用go语言开发的服务发现.配置管理中心服务.目前公司用的是这个东西去管理项目上的一些配置信息.公司的环境是通过docker镜像的方式去部署的,镜像是通过rancher去进行管理的.这一套东西面临的一个问题是:服务每次更新之后,服务对应的ip地址是动态变化的.每次需要使用swagger去测接口的时候,都要去rancher上去重新找新的ip地址,比较麻烦.正好呢,最近部门在考虑准备做

  • python实现提取jira bug列表的方法示例

    目录 公司要求内部每日整理jira bug发邮件,手动执行了一段时间,想着用自动化的方式实现,故用了3天的时间做出了此脚本. 第一版基础版 # -*- coding:utf-8 -*- import requests import re from bs4 import BeautifulSoup as bs import time import os jql = "project = SDP and parent = SDP-13330 AND issuetype in (standardIss

  • python实现最大子序和（分治+动态规划）

    给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和. 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6. 进阶: 如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解. 思路: 首先我们分析题目,我们思考,为什么最大和的连续子数组不包含其他的元素而是这几个呢?因为如果我们想在现有的基础上去扩展当前连续子数组,相邻的元素是一定要被加入的,而相邻

随机推荐