首页 > Python教程 > 正文

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

原创 2017-12-06 10:42:58 0 106
赞助会员专享特权
求最大连续子序列的和是一个很经典很古老的面试题了,本文我们就和大家分享关于用Python语言描述最大连续子序列和方法,希望能帮助到大家。

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语言描述最大连续子序列和的详细内容,更多请关注php中文网其它相关文章!

  • 相关标签:Python 连续 最大
  • 本文原创发布php中文网 ,转载请注明出处,感谢您的尊重!
  • 相关文章


  • 在Django框架中运行Python应用全攻略
  • 在Python的Django框架中创建和使用模版
  • python获取元素在数组中索引号的方法
  • 浅谈python中截取字符函数strip,lstrip,rstrip
  • 用Python语言描述最大连续子序列和
  • 网友评论

    文明上网理性发言,请遵守 新闻评论服务协议

    我要评论
    独孤九贱(4)_PHP视频教程

    独孤九贱(4)_PHP视频教程

    江湖传言:PHP是世界上最好的编程语言。真的是这样吗?这个梗究竟是从哪来的?学会本课程,你就会明白了。 PHP中文网出品的PHP入门系统教学视频,完全从初学者的角度出发,绝不玩虚的,一切以实用、有用...

    独孤九贱(5)_ThinkPHP5视频教程

    独孤九贱(5)_ThinkPHP5视频教程

    ThinkPHP是国内最流行的中文PHP开发框架,也是您Web项目的最佳选择。《php.cn独孤九贱(5)-ThinkPHP5视频教程》课程以ThinkPHP5最新版本为例,从最基本的框架常识开始,将...

    独孤九贱(1)_HTML5视频教程

    独孤九贱(1)_HTML5视频教程

    《php.cn原创html5视频教程》课程特色:php中文网原创幽默段子系列课程,以恶搞,段子为主题风格的php视频教程!轻松的教学风格,简短的教学模式,让同学们在不知不觉中,学会了HTML知识。 ...

    ThinkPHP5实战之[教学管理系统]

    ThinkPHP5实战之[教学管理系统]

    本套教程,以一个真实的学校教学管理系统为案例,手把手教会您如何在一张白纸上,从零开始,一步一步的用ThinkPHP5框架快速开发出一个商业项目。

    PHP入门视频教程之一周学会PHP

    PHP入门视频教程之一周学会PHP

    所有计算机语言的学习都要从基础开始,《PHP入门视频教程之一周学会PHP》不仅是PHP的基础部分更主要的是PHP语言的核心技术,是学习PHP必须掌握的内容,任何PHP项目的实现都离不开这部分的内容,通...

    相关视频教程

  • javascript初级视频教程 javascript初级视频教程
  • jquery 基础视频教程 jquery 基础视频教程
  • javascript三级联动视频教程 javascript三级联动视频教程
  • 独孤九贱(3)_JavaScript视频教程 独孤九贱(3)_JavaScript视频教程
  • 独孤九贱(6)_jQuery视频教程 独孤九贱(6)_jQuery视频教程
  • 相关视频章节