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

meistudios

经典的动态规划问题。
定义f为所有可能的 k 中 a[k] + ... + a 最大的那个和。
那么很显然：
f[1] = a[1 ...
meistudios 发表于 2011-06-06 19:38

    这是我的代码：

1. 
   
2. def MaxSum(l):
   
3.   if not l:
   
4.     return 0
   
5.   f = l[0]
   
6.   max = l[0]
   
7.   for a in l[1:]:
   
8.     if f > 0:
   
9.       f += a
   
10.     else:
    
11.       f = a
    
12.     if f > max:
    
13.       max = f
    
14.   return max
    

复制代码