最近有道面试题很流行:
给定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/python import 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. 原文链接:http://edu./2010/1030/26833.php |
|