给定随机整形数列求最大子段和Python代码

时间：2010-10-23 来源：donotblock

最近有道面试题很流行：
给定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))