自我修养►数据结构与算法

求最大子数组---python实现

动态规划求一个数组的最大子数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def max_sub_array(a):  
    sum, max, start, new_start, end = a[0], a[0], 0, 0, 0  
    for i, e in enumerate(a[1:], 1):  
        if sum <= 0:  
            new_start = i  
            sum = e  
        else:  
            sum += e  
  
        if sum > max:  
            start = new_start  
            end = i  
            max = sum  
    return start, end, max