求数值数组中连续和最大的子数组

1.分析

　　首先，这样的数组一定是有正负数组成的，这样问题才有意义。要求解这个问题，可以使用分治思想将所求问题的规模变小，通过求解子问题的解来最终得到所求问题的解，显然每个子问题和原问题相同，可以用递归来进行求解。

我们知道，通过将数组一分为二后，最大子数组有以下三种位置：

存在于左子数组中
存在于右子数组中
跨越中点，存在于左右两个子数组中

2.使用递归进行求解

 1 def findMaxCrossSubarray(L,low,mid,high):
 2     left_sum = -float("inf")
 3     Sum = 0
 4     for i in range(mid,low -1,-1):
 5         Sum = Sum + L[i]
 6         if Sum > left_sum:
 7             left_sum = Sum
 8             left_max = i
 9 
10     right_sum = -float("inf")
11     Sum = 0
12     for j in range(mid+1,high+1):
13         Sum = Sum + L[j]
14         if Sum > right_sum:
15             right_sum = Sum
16             right_max = j
17 
18     return (left_max,right_max,left_sum + right_sum)
19 
20 
21 
22 def findMaxSubarray(L,low,high):
23     if low == high:
24         return (low,high,L[low])
25     else:
26         mid = (low + high) / 2
27         (left_i,left_j,left_sum) = findMaxSubarray(L,low,mid)
28         (right_i,right_j,right_sum) = findMaxSubarray(L,mid+1,high)
29         (cross_i,cross_j,cross_sum) = findMaxCrossSubarray(L,low,mid,high)
30 
31         if left_sum >= right_sum and left_sum >= cross_sum:
32             return (left_i,left_j,left_sum)
33         elif right_sum >= left_sum and right_sum >= cross_sum:
34             return (right_i,right_j,right_sum)
35         else:
36             return (cross_i,cross_j,cross_sum)
37 
38 if __name__ == "__main__":
39     L = [3,-2,8,-3,-5,3]
40     low = 0
41     high = len(L) - 1
42     print findMaxSubarray(L,low,high)

参考：算法导论（p40)

3. 最优解法

　　要求最大连续和最大的子数组和，我们的第一个元素必须要大于0

def FindMaxSubarray(L):
    lenght = len(L)
    Max_subarray_value = 0
    current = 0
    for item in L:
        current += item
        if current > 0:

            if current > Max_subarray_value:

                Max_subarray_value = current
        else:
            current = 0

    return Max_subarray_value

if __name__ == "__main__":
    L = [-1,2,-1,3]
    print FindMaxSubarray(L)