Python语言描述最大连续子序列和
作者:bitcarmanlee 时间:2023-10-03 20:16:24
求最大连续子序列的和是一个很经典很古老的面试题了,记得在刚毕业找工作面试那会也遇到过同款问题。今儿突然想起来,正好快到毕业季,又该是苦逼的应届生们各种面试的时候到了,就给写了一些小代码解决这个问题。也希望各位找工作的同志们都拿到心目中理想的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+mongodb数据抓取详细介绍
如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!
来源:http://blog.csdn.net/bitcarmanlee/article/details/51526010
标签:python,序列,面试题
0
投稿
猜你喜欢
Linux下如何实现Mysql定时任务
2024-01-19 09:41:50
SpringSecurity从数据库中获取用户信息进行验证的案例详解
2024-01-23 17:16:25
python基础之并发编程(二)
2023-01-16 03:10:37
php 字符串函数收集
2024-05-11 10:02:26
Python调用Jar包的两种方式小结
2023-07-26 06:29:12
go doudou应用中使用注解示例详解
2024-02-23 08:35:07
python-web根据元素属性进行定位的方法
2021-05-04 04:22:35
快速解决 MySQL中与浮点比较有关的问题
2008-11-27 16:28:00
Python合并字典键值并去除重复元素的实例
2022-02-10 17:48:40
Python 解析XML文件
2021-12-08 02:24:46
windows无法启动MySQL服务报错1067的解决方法
2024-01-19 09:07:01
python中reduce()函数的使用方法示例
2021-08-09 12:32:53
Python基础之numpy库的使用
2023-01-21 02:48:51
Python 打印中文字符的三种方法
2022-11-14 10:22:07
学生如何注册Pycharm专业版以及pycharm的安装
2023-01-20 15:43:40
linux/mac安装mysql忘记密码的解决办法
2024-01-23 23:40:06
ASP 使用三层架构 asp中使用类
2011-03-16 10:52:00
python爱心表白 每天都是浪漫七夕!
2023-02-26 20:36:55
基于Python实现人脸识别和焦点人物检测功能
2021-03-09 10:27:45
在Python中使用判断语句和循环的教程
2022-06-03 22:31:27