实现了两种,一种是算出最大值,一种是把最大值的子数组打印出来,时间复杂度都是o(n),空间复杂度o(1)
#! /usr/bin/env python
#coding=utf-8
def maxArray(a):
print sum(a)
maxV=a[-1]
tempV=a[-1]
for i in xrange(len(a)-2,-1,-1):
tempV=max([a[i],tempV+a[i]])
maxV=max([maxV,tempV])
print maxV
def maxArrayLog(a):
#print sum(a)
maxV=a[-1]
maxA=[a[-1]]
tempV=a[-1]
tempA=[a[-1]]
for i in xrange(len(a)-2,-1,-1):
if a[i]>tempV+a[i]:
tempV=a[i]
tempA=[]
else:
tempV+=a[i]
tempA.append(a[i])
if maxV<tempV:
maxV=tempV
maxA=list(tempA)
maxA.reverse()
print maxV
print maxA
maxArrayLog([-2,1,2,-41,-23,14,-23,-5,35,-3,63,-63,7,4,6])
分享到:
相关推荐
的值 52<br><br>0069 求最大公约数 52<br><br>0070 求最小公倍数 53<br><br>0071 判断素数的算法 53<br><br>0072 如何判断一个数是否是完数 54<br><br>0073 歌德巴赫猜想的算法 54<br><br>0074 八皇后...
列的最大值<br>3.6.2. 拥有某个列的最大值的行<br>3.6.3. 列的最大值:按组<br>3.6.4. 拥有某个字段的组间最大值的行<br>3.6.5. 使用用户变量<br>3.6.6. 使用外键<br>3.6.7. 根据两个键搜索<br>3.6.8. 根据天计算...
该函数使用一个 for 循环遍历数组中的每个元素,并根据算法中的步骤来更新最大元素和第二大元素。最后,该函数返回第二大元素的值。还编写一些测试用例程序来测试我的代码,以确保它能够正常工作并返回正确的结果。...
对于在两个非常大的数组上快速完成相同工作并具有一些附加功能的函数,请参阅 Jos 的 NEARESTPOINT: www.mathworks.com/matlabcentral/fileexchange/8939 左上角的图显示了最大值。 'Vals' 的长度与 'X' 的长度,...
Checking a remote server for identd<rojy bug> 13-6. pidof 帮助杀掉一个进程 13-7. 检查一个CD 镜像 13-8. 在一个文件中创建文件系统 13-9. 添加一个新的硬盘驱动器 13-10. 使用umask 来将输出文件隐藏起来 13-...
<<page 1>> page begin==================== 目 目目 目 录 录录 录 第一部分 C#语言概述.4 第一章 第一章第一章 第一章 .NET 编 编 编程语言 程语言编程语言 程语言 C#.4 1.1 Microsoft...
面向对象的编程语言将客观事物看作具有属性和行为的对象,通过抽象找出同一类对象的共同属性(静态特征)和行为(动态特征),形成类。通过类的继承与多态可以很方便地实现代码重用,大大缩短了软件开发周期,并使得...
队列的最大值.py n个骰子的点数.py 扑克牌中的顺子.py 圆圈中最后剩下的数字.py 股票的最大利润.py 求1+2+…+n.py 不用加减乘除做加法.py 构建乘积数组.py 把字符串转换成整数.py 树中两个节点的最低公共祖先.py
由最长公共子序列问题的最优子结构性质可知,要找出X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的最长公共子序列,可按以下方式递归地进行:当xm=yn时,找出Xm-1和Yn-1的最长公共子序列,然后在其尾部加上xm(=yn)即可得...
在满二叉树中,每一层上的结点数都达到最大值,即在满二叉树的第k层上有2k-1个结点,且深度为m的满二叉树有2m-1个结点。 完全二叉树是指这样的二叉树:除最后一层外,每一层上的结点数均达到最大值;在最后一层上只...
cout<<" "<<a<<'+'<<b<<'='; int r; cin>>r; if(r!=a+b) { cout<<" "<<"╳ 很遗憾,回答错误! X﹏X "<<endl; return -1; } else { cout<<" "<<"√ 恭喜你回答正确!↘(^ω^)↙"<...
当一个正则表达式成功地和目标字符串相匹配时,可以从目标串中抽出和括号中的子模式相匹配 的部分.例如,假定我们正在检索的模式是一个或多个字母后面跟随一位或多位数字,那么我们可以使用模式 / [a-z] + \ d+/.但是...
每次到了期末,要统计各科成绩,是一件不小的事情,以这程序为模板,可以修改成自己所要的资料,减小了不少的工作量
algorithm#记录算法学习的历程与实现#一....用最大堆实现优先队列(priority queue)实现INSERT(S,x) 把x插入S队列中实现MAXIMUM(S)返回S中最大值实现EXTRACT_MAX(S) 删除最大值并且返回实现INCREASE_KEY(S,x,key
leetcode数组下标大于间距 算法学习 排序 种类 时间复杂度(平均) 方法 完成度 冒泡排序 O(n2) sort.Bubble √ 选择排序 O(n2) sort.Select √ 直接插入排序 O(n2) sort.DirectInsert √ 折半查找排序 O(n2) sort....
leetcode二维数组搜索面试问题 亚马逊 行为的 你最大的成就是什么 你如何评估你现在的老板,他需要改进的地方。...在全年未排序的股票价格数组中,找出买入和卖出的时间点,以实现利润最大化。 您将如何比较具有
i:=n*n WHILE i<>1 DO i:=i div 2; 14. 计算机执行下面的语句时,语句 s的执行次数为 _______ 。【南京理工大学 2000二、1(1.5分)】 FOR(i=l;i<n-l;i++) FOR(j=n;j>=i;j--) s; 15. 下面程序段的时间...
1.23 能否声明和传入数组大小一致的局部数组,或者由其他参数指定大小的参数数组? 1.24 我在一个文件中定义了一个extern数组,然后在另一个文件中使用,为什么sizeof取不到数组的大小? 声明问题 1.25 函数只...
1.23 能否声明和传入数组大小一致的局部数组,或者由其他参数指定大小的参数数组? 13 1.24 我在一个文件中定义了一个extern数组,然后在另一个文件中使用,为什么sizeof取不到数组的大小? 13 声明问题 14 ...