首页 手机软件 手机游戏 单机游戏 资讯文章 专题下载 游戏合集 文章合集 php下载 php教程 电脑软件
+ -
当前位置：首页 → 问答吧 → 求随机数列字串最大和问题Python解法

求随机数列字串最大和问题Python解法

时间：2010-10-23

来源：互联网

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

贴个Python解法：
  1. #!/usr/bin/python
  2. import sys
  3. def getMax(array):
  4.   maxV=None;
  5.   maxL=[]
  6.   start = 0
  7.   end = 0
  8.   for n in range(len(array)):
  9.     l=[]
  10.     v=0
  11.     for i in array[n:]:
  12.       l=l[:]
  13.       l.append(i)
  14.       v=v+i
  15.       if(v>maxV or maxV==None):
  16.         maxV=v
  17.         maxL=l
  18.         start = n
  19.         end = n+array[n:].index(i)
  20.   
  21.   print("Start: %s, End: %s" % (start, end))
  22.   print(maxV)

  24. def getMax2(array):
  25.   tempSum = None
  26.   Sum = None
  27.   start = 0
  28.   end = 0
  29.   tempStart = 0
  30.   for n in range(len(array)):
  31.     if tempSum>0 or tempSum>array[n]:
  32.       tempSum = tempSum+array[n]
  33.     else:
  34.       tempSum = array[n]
  35.       tempStart = n
  36.    
  37.     if tempSum>Sum:
  38.       start = tempStart
  39.       Sum=tempSum
  40.       end = n

  42.   #print(array[start:end+1])
  43.   print("Start: %s, End: %s" % (start, end))
  44.   print(Sum)

  46. if __name__=="__main__":
  47.   getMax([int(x) for x in sys.argv[1].split(",")])
  48.                                                                                                                         
复制代码
getMax是最简单直观的两层循环穷举
getMax2是动态规划算法:

再来个测试脚本：
  1. #!/usr/bin/python

  3. import random
  4. import sys
  5. import time
  6. from getMax import *

  8. def getRandomList(num):
  9.   if not num:
  10.    length = random.randint(1,1000)
  11.   else:
  12.    length = num

  14.   l=[]
  15.   for i in range(length):
  16.     l.append(random.randint(-1000000,1000000))

  18.   return l


  21. if __name__=="__main__":
  22.   for i in range(10):
  23.     l = getRandomList(None)
  24.     print("")
  25.     print("********")
  26.     print("Length of test data: %s" % len(l))
  27.     print("Method: getMax")
  28.     start=time.time()
  29.     getMax(l)
  30.     print("Used time: %s" % (time.time()-start))
  31.     print("")
  32.     print("Method: getMax2")
  33.     start=time.time()
  34.     getMax2(l)
  35.     print("Used time: %s" % (time.time()-start))
  36. ~                                                   
复制代码
初学Python，code style就那样儿，估计说的还不是地道的Python方言

作者: donotblock   发布时间: 2010-10-23

不错呵,初学能写出这些代码

作者: a515200a   发布时间: 2010-10-24

相关阅读 更多

热门阅读

热门下载

更多
关于本站 免责申明 联系我们

Copyright 2006-2020 php爱好者(phpfans.net) All Rights Reserved.备案号：湘ICP备2023016114号-2

本站为非盈利性网站，不接受任何广告。本站所有资源均由网友上传，如有侵权，请发邮件至 [email protected] phpfans.net