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

求最大连续子序列的和是一个很经典很古老的面试题了，记得在刚毕业找工作面试那会也遇到过同款问题。今儿突然想起来，正好快到毕业季，又该是苦逼的应届生们各种面试的时候到了，就给写了一些小代码解决这个问题。也希望各位找工作的同志们都拿到心目中理想的offer，从此以后，战胜高富帅，赢取白富美，走上人生巅峰。

1.问题描述

假设有一数组（python里为list啦）[1,3,-3,4,-6,-1]，求数组中最大连续子序列的和。例如在此数组中，最大连续子序列的和为5，即1+3+（-3）+4 = 5

2.O(n2)的解法

最简单粗暴的方式，双层循环，用一个maxsum标识最大连续子序列和。然后每次判断更新。没有太多可以说的，直接上代码

def maxSum(list):
  maxsum = list[0]
  for i in range(len(list)):
    maxtmp = 0
    for j in range(i,len(list)):
      maxtmp += list[j]
      if maxtmp > maxsum:
        maxsum = maxtmp
  return maxsum
if __name__ == '__main__':
  list = [1,3,-3,4,-6]
  maxsum = maxSum(list)
  print "maxsum is",maxsum

运行结果

maxsum is 5

3.O(n)解法

在任何讲动态规范的地方都能找到求最大连续子序列和的例子。具体来说，假设数组为a[i]，因为最大连续的子序列和必须是在位置0-(n-1)之间的某个位置结束。那么，当循环遍历到第i个位置时，如果其前面的连续子序列和小于等于0，那么以位置i结尾的最大连续子序列和就是第i个位置的值即a[i]。如果其前面的连续子序列和大于0，则以位置i结尾的最大连续子序列和为b[i] = max{ b[i-1]+a[i]，a[i]}，其中b[i]就是指最大连续子序列的和。

def maxSum(list_of_nums):
  maxsum = 0
  maxtmp = 0
  for i in range(len(list_of_nums)):
    if maxtmp <= 0:
      maxtmp = list_of_nums[i]
    else:
      maxtmp += list_of_nums[i]

    if(maxtmp > maxsum):
      maxsum = maxtmp
  return maxsum
if __name__ == '__main__':
  list_of_num = [1,3,-3,4,-6]
  maxsum = maxSum(list_of_num)
  print "maxsum is: ",maxsum

运行结果

maxsum is 5

总结

以上就是本文关于Python语言描述最大连续子序列和的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站：

Python生成数字图片代码分享

python数字图像处理之高级滤波代码详解

python+mongodb数据抓取详细介绍

如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！

赞 (0)

相关推荐

  • Python的Django REST框架中的序列化及请求和返回

    序列化Serialization 1. 设置一个新的环境 在我们开始之前, 我们首先使用virtualenv要创建一个新的虚拟环境,以使我们的配置和我们的其他项目配置彻底分开. $mkdir ~/env $virtualenv ~/env/tutorial $source ~/env/tutorial/bin/avtivate 现在我们处在一个虚拟的环境中,开始安装我们的依赖包 $pip install django $pip install djangorestframework $pip i

  • 详解python中executemany和序列的使用方法

    详解python中executemany和序列的使用方法 一 代码 import sqlite3 persons=[ ("Jim","Green"), ("Hu","jie") ] conn=sqlite3.connect(":memory:") conn.execute("CREATE TABLE person(firstname,lastname)") conn.executeman

  • 详解Python 序列化Serialize 和 反序列化Deserialize

    详解Python 序列化Serialize 和 反序列化Deserialize 序列化 (serialization) 序列化是将对象状态转换为可保持或传输的格式的过程.与序列化相对的是反序列化, 它将流转换为对象.这两个过程结合起来,可以轻松地存储和传输数据. 序列化和反序列化的目的 1.以某种存储形式使自定义对象持久化: 2.将对象从一个地方传递到另一个地方. 3.使程序更具维护性 序列化   由于存在于内存中的对象都是暂时的,无法长期驻存,为了把对象的状态保持下来,这时需要把对象写入到磁盘

  • 浅析python中的分片与截断序列

    序列概念 在分片规则里list.tuple.str(字符串)都可以称为序列,都可以按规则进行切片操作 切片操作 注意切片的下标0代表顺序的第一个元素,-1代表倒序的第一个元素:且切片不包括右边界,例如[0:3]代表元素0.1.2不包括3. l=['a','b','c','d',5] 1.获取列表的前3个元素 >>> l[0:3] ['a', 'b', 'c'] >>> l[:3] ['a', 'b', 'c'] 2.获取列表的后3个元素 >>> l[-

  • Python 序列的方法总结

    最近在做Python 的项目,特地整理了下 Python 序列的方法.序列sequence是python中最基本的数据结构,本文先对序列做一个简单的概括,之后简单讲解下所有序列都能通用的操作方法. 任何序列都可以引用其中的元素(item). 下面的内建函数(built-in function)可用于列表(表,定值表,字符串) #s为一个序列 len(s) 返回: 序列中包含元素的个数 min(s) 返回:序列中最小的元素 max(s) 返回:序列中最大的元素 all(s) 返回:True,若果所

  • python魔法方法-自定义序列详解

    python魔法方法-自定义序列详解

    自定义序列的相关魔法方法允许我们自己创建的类拥有序列的特性,让其使用起来就像 python 的内置序列(dict,tuple,list,string等). 如果要实现这个功能,就要遵循 python 的相关的协议.所谓的协议就是一些约定内容.例如,如果要将一个类要实现迭代,就必须实现两个魔法方法:__iter__.next(python3.x中为__new__).__iter__应该返回一个对象,这个对象必须实现 next 方法,通常返回的是 self 本身.而 next 方法必须在每次调用的时

  • Python常用的内置序列结构(列表、元组、字典)学习笔记

    列表与元组 列表用大括号[]表示,元组用圆括号()表示. 列表可以修改,字符串与元组不可修改. 元组的分片还是元组,列表的分片还是列表. 1.列表方法: name=["zhang3","li4","wang5"] name.append("gou6") #添加项 name.remove("gou6") #移除第一个匹配项,也可用del name[3]来移除 name.insert(3,"gou6&

  • Python序列化基础知识（json/pickle）

    我们把对象(变量)从内存中变成可存储的过程称之为序列化,比如XML,在Python中叫pickling,在其他语言中也被称之为serialization,marshalling,flattening等等,都是一个意思. 序列化后,就可以把序列化后的内容写入磁盘,或者通过网络传输到其他服务器上,反过来,把变量内容从序列化的对象重新读到内存里称之为反序列化,即unpickling json(JavaScript Object Notation) 一种轻量级的数据交换格式.它基于ECMAScript的

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

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

  • Python语言描述连续子数组的最大和

    题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学.今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决.但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止).你会不会被他忽悠住?(子向量的长度至少是1) 思路: 最大和连续子数组一定有如下几个特点: 1.第一个不为负数 2.如果前面数的累加值

  • Python语言描述KNN算法与Kd树

    Python语言描述KNN算法与Kd树

    最近邻法和k-近邻法 下面图片中只有三种豆,有三个豆是未知的种类,如何判定他们的种类? 提供一种思路,即:未知的豆离哪种豆最近就认为未知豆和该豆是同一种类.由此,我们引出最近邻算法的定义:为了判定未知样本的类别,以全部训练样本作为代表点,计算未知样本与所有训练样本的距离,并以最近邻者的类别作为决策未知样本类别的唯一依据.但是,最近邻算法明显是存在缺陷的,比如下面的例子:有一个未知形状(图中绿色的圆点),如何判断它是什么形状? 显然,最近邻算法的缺陷--对噪声数据过于敏感,为了解决这个问题,我们可

  • Python语言描述机器学习之Logistic回归算法

    Python语言描述机器学习之Logistic回归算法

    本文介绍机器学习中的Logistic回归算法,我们使用这个算法来给数据进行分类.Logistic回归算法同样是需要通过样本空间学习的监督学习算法,并且适用于数值型和标称型数据,例如,我们需要根据输入数据的特征值(数值型)的大小来判断数据是某种分类或者不是某种分类. 一.样本数据 在我们的例子中,我们有这样一些样本数据: 样本数据有3个特征值:X0X0,X1X1,X2X2 我们通过这3个特征值中的X1X1和X2X2来判断数据是否符合要求,即符合要求的为1,不符合要求的为0. 样本数据分类存放在一个

  • Python语言描述随机梯度下降法

    Python语言描述随机梯度下降法

    1.梯度下降 1)什么是梯度下降? 因为梯度下降是一种思想,没有严格的定义,所以用一个比喻来解释什么是梯度下降. 简单来说,梯度下降就是从山顶找一条最短的路走到山脚最低的地方.但是因为选择方向的原因,我们找到的的最低点可能不是真正的最低点.如图所示,黑线标注的路线所指的方向并不是真正的地方. 既然是选择一个方向下山,那么这个方向怎么选?每次该怎么走? 先说选方向,在算法中是以随机方式给出的,这也是造成有时候走不到真正最低点的原因. 如果选定了方向,以后每走一步,都是选择最陡的方向,直到最低点.

  • 利用C语言来求最大连续子序列乘积的方法

    利用C语言来求最大连续子序列乘积的方法

    题目描述:给一个浮点数序列,取最大乘积连续子串的值,例如 -2.5,4,0,3,0.5,8,-1,则取出的最大乘积连续子串为3,0.5,8.也就是说,上述数组中,3 0.5 8这3个数的乘积3*0.5*8=12是最大的,而且是连续的. 提醒:此最大乘积连续子串与最大乘积子序列不同,请勿混淆,前者子串要求连续,后者子序列不要求连续.也就是说:最长公共子串(Longest CommonSubstring)和最长公共子序列(LongestCommon Subsequence,LCS)的区别: 子串(S

  • Python语言实现机器学习的K-近邻算法

    Python语言实现机器学习的K-近邻算法

    写在前面 额...最近开始学习机器学习嘛,网上找到一本关于机器学习的书籍,名字叫做<机器学习实战>.很巧的是,这本书里的算法是用Python语言实现的,刚好之前我学过一些Python基础知识,所以这本书对于我来说,无疑是雪中送炭啊.接下来,我还是给大家讲讲实际的东西吧. 什么是K-近邻算法? 简单的说,K-近邻算法就是采用测量不同特征值之间的距离方法来进行分类.它的工作原理是:存在一个样本数据集合,也称作训练样本集,并且样本集中每个数据都存在标签,即我们知道样本集中每一数据与所属分类的对应关系

  • 浅析Python语言自带的数据结构有哪些

    Python作为一种脚本语言,其要求强制缩进,使其易读.美观,它的数据类型可以实现自动转换,而不需要像C.Java那样给变量定义数据类型,使其编写非常方便简单,所以广受大家的欢迎. 现如今,Python已经广泛的应用于数据分析.数据挖掘.机器学习等众多科学计算领域.所以既然涉及到科学计算,深入了解Python原生提供的数据结构是很有必要的,这样才能在数据的海洋中游刃有余.得心应手.本文便以此展开,做一个归纳整理,方便收藏. Python 一.序列结构 首先介绍的数据结构是序列结构,所谓序列,也就

  • python语言中有算法吗

    了解算法之前,我们先看一下什么是算法 定义:算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制.也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出.如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题.不同的算法可能用不同的时间.空间或效率来完成同样的任务.一个算法的优劣可以用空间复杂度与时间复杂度来衡量. python中的常见算法 冒泡排序 效率:O(n2) 原理: 比较相邻的元素,如果

  • Python descriptor(描述符)的实现

    问题 问题1 Python是一种动态语言,不支持类型检查.当需要对一个对象执行类型检查时,可能会采用下面的方式: class Foo(object): def __init__(self,a): if isinstance(a,int): self.__a = a else: raise TypeError("Must be an int") def set_a(self,val): if isinstance(val,int): self.__a = val else: raise

随机推荐