豪华曹操传2014成都:python 数列

来源：百度文库编辑：九乡新闻网时间：2024/04/29 07:20:01

最近有道面试题很流行：
给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n],求该序列如a+a[i+1]+…+a[j]的子段和的最大值贴个Python解法：

getMax是最简单直观的两层循环穷举
getMax2是动态规划算法: #!/usr/bin/python
import sys
def getMax(array):
maxV=None;
maxL=[]
start = 0
end = 0
for n in range(len(array)):
    l=[]
    v=0
    for i in array[n:]:
      l=l[:]
      l.append(i)
      v=v+i
      if(v>maxV or maxV==None):
        maxV=v
        maxL=l
        start = n
        end = n+array[n:].index(i) print("Start: %s, End: %s" % (start, end))
print(maxV)def getMax2(array):
tempSum = None
Sum = None
start = 0
end = 0
tempStart = 0
for n in range(len(array)):
    if tempSum>0 or tempSum>array[n]:
      tempSum = tempSum+array[n]
    else:
      tempSum = array[n]
      tempStart = n    if tempSum>Sum:
      start = tempStart
      Sum=tempSum
      end = n #print(array[start:end+1])
print("Start: %s, End: %s" % (start, end))
print(Sum)if __name__=="__main__":
getMax([int(x) for x in sys.argv[1].split(",")]) 测试脚本:
#!/usr/bin/pythonimport random
import sys
import time
from getMax import *def getRandomList(num):
if not num:
   length = random.randint(1,1000)
else:
   length = num l=[]
for i in range(length):
    l.append(random.randint(-1000000,1000000)) return l
if __name__=="__main__":
for i in range(10):
    l = getRandomList(None)
    print("")
    print("********")
    print("Length of test data: %s" % len(l))
    print("Method: getMax")
    start=time.time()
    getMax(l)
    print("Used time: %s" % (time.time()-start))
    print("")
    print("Method: getMax2")
    start=time.time()
    getMax2(l)
    print("Used time: %s" % (time.time()-start))

本篇文章来源于：开发学院 http://edu.codepub.com   原文链接：http://edu.codepub.com/2010/1030/26833.php

python 数列 python 菲波那契数列 Python python 高中数学数列数列求和 [Python]python随笔 [Python]Python笔记- [Python]python编程 FAQ [Python]C#程序员初学Python [Python]Python连接MySQL (例子) [Python]python for ARM/LINUX [Python]MySQLdb for Python使用指南 [Python]用Python操作Mysql 分数数列的拆分费氏黄金数列高中代数-数列数列课堂实录（简版）高中数学数列所有公式 Python raw_input 读取输入值 [Python俱乐部] [Python]年度黑马Python 自省指南 [Python]Python完全新手教程 -- 1 [Python]Python完全新手教程 -- 2 [Python]Python完全新手教程 -- 3