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

donotblock

最近有道面试题很流行：
给定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)
    
23. 
    
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
    
41. 
    
42.   #print(array[start:end+1])
    
43.   print("Start: %s, End: %s" % (start, end))
    
44.   print(Sum)
    
45. 
    
46. if __name__=="__main__":
    
47.   getMax([int(x) for x in sys.argv[1].split(",")])
    
48.                                                                                                                         
    

复制代码

getMax是最简单直观的两层循环穷举
getMax2是动态规划算法:

再来个测试脚本：

1. #!/usr/bin/python
   
2. 
   
3. import random
   
4. import sys
   
5. import time
   
6. from getMax import *
   
7. 
   
8. def getRandomList(num):
   
9.   if not num:
   
10.    length = random.randint(1,1000)
    
11.   else:
    
12.    length = num
    
13. 
    
14.   l=[]
    
15.   for i in range(length):
    
16.     l.append(random.randint(-1000000,1000000))
    
17. 
    
18.   return l
    
19. 
    
20. 
    
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方言{:3_196:}

a515200a

:wink: 不错呵,初学能写出这些代码
不过对于求最大子段和,用递归会好很多,且能简化代码

1. def root(x,s=1,k=0,q=[]):
   
2.         if s is len(x)-1:
   
3.            print '最大子段和为%s'%max(q)
   
4.         else:
   
5.            h = 0
   
6.            for i in range(len(x),s,-1):
   
7.                for j in range(k,i):
   
8.                    h += x[j]
   
9.                q.append(h)
   
10.                h = 0
    
11.            return root(x,s+1,k+1)

复制代码

不过这段代码存在一点问题,应该改改!

donotblock

回复 2# a515200a

学习了，这个应该是那个双层循环的递归形式
递归对我来说还不娴熟，很多能用递归简化的地方都想不起来 :wink:

a515200a

嘿嘿!

a515200a

最后改了一下,应该没问题了

1. def root(x,s=0,k=0):
   
2.         if s is 0:
   
3.            global q
   
4.            q = list()
   
5.         if len(x) is 2 : print '最大子段和为%s'%(x[0]+x[1])
   
6.         else:
   
7.            if s is len(x)-1:
   
8.               print '最大子段和为%s'%max(q)
   
9.               del q
   
10.            else:
    
11.               h = 0
    
12.               for i in range(len(x),s,-1):
    
13.                   for j in range(k,i):
    
14.                       h += x[j]
    
15.                   q.append(h)
    
16.                   h = 0
    
17.               return root(x,s+1,k+1)

复制代码

如果在函数里面引用默认参数列表来保存元素,会永远的保存下去,这显然不行.局部变量的话递归时会被重新赋值,只能引用到全局了~不知有没有其他解决办法,!

a515200a

再次修改了一下,代码简化更多

1. def word(x):
   
2.         def root(x,s=0,k=0,q=[]):
   
3.             if s is len(x)-1 : print '最大子段和为%s'%max(q)
   
4.             else:
   
5.                h = 0
   
6.                for i in range(len(x),s,-1):
   
7.                    for j in range(k,i):
   
8.                        h += x[j]
   
9.                    q.append(h)
   
10.                    h = 0
    
11.                return root(x,s+1,k+1)
    
12.         return root(x)

复制代码

donotblock

回复 6# a515200a

这就是函数里面可以定义函数的好处么

a515200

是呀,嵌套,每次调用word都重新生成内部函数root,把root的默认参数总是保存元素给和谐了.....

a515200

几个月前的老贴了，再次贴下更改进的算法

1. def root(x,s=0,k=0,q=[]):
   
2.         for s in range(len(x)-1):
   
3.              h = 0
   
4.              for i in range(len(x),s,-1):
   
5.                  for j in range(k,i):
   
6.                      h+=x[j]
   
7.                  q.append(h)
   
8.                  h = 0
   
9.              k += 1
   
10.         print '最大子段和为%s'%max(q)

复制代码

三层循环，说实话，为什么这个算法能解决这个问题，我自己都搞不懂原理，大概知道是枚举之类的算法了

meistudios

[i=s] 本帖最后由 meistudios 于 2011-06-06 19:46 编辑 [/i]

经典的动态规划问题。
定义f[i]为所有可能的 k 中 a[k] + ... + a[i] 最大的那个和。
那么很显然：
f[1] = a[1].
f[i+1] = max(f[i] + a[i+1], a[i+1]).
一个简单循环，就可以顺次常数时间求出f[1]一直到f[n].其实你不需要记录所有的这n个f值。你只要一个最大的f值，它就是所有可能的子序列里的最大和。
一个循环，时间复杂度O(n).