求最大连续子序列的和是一个很经典很古老的面试题了，记得在刚毕业找工作面试那会也遇到过同款问题。今儿突然想起来，正好快到毕业季，又该是苦逼的应届生们各种面试的时候到了，就给写了一些小代码解决这个问题。也希望各位找工作的同志们都拿到心目中理想的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数据抓取详细介绍
如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！ 如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
《魔兽世界》大逃杀！60人新游玩模式《强袭风暴》3月21日上线
暴雪近日发布了《魔兽世界》10.2.6 更新内容，新游玩模式《强袭风暴》即将于3月21 日在亚服上线，届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。
艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕，并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时，他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中，玩家将会进入一个全新的海盗主题大逃杀式限时活动，其中包含极高的风险和史诗级的奖励。
《强袭风暴》不是普通的战场，作为一个独立于主游戏之外的活动，玩家可以用大逃杀的风格来体验《魔兽世界》，不分职业、不分装备（除了你在赛局中捡到的），光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式，玩家在加入海盗主题的预赛大厅区域前，可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹，《巨龙崛起》和《魔兽世界：巫妖王之怒 经典版》的玩家都可以获得奖励。