1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| import random
def find_max_crossing_subarray(A, low, mid, high):
"""
求跨越两个数组的最大字数组
:param A:
:param low:
:param mid:
:param high:
:return:
"""
left_sum = A[mid]
left_index = mid
sum = 0
for left in range(mid, low - 1, -1):
sum = sum + A[left]
if sum > left_sum:
left_sum = sum
left_index = left
right_sum = A[mid + 1]
right_index = mid + 1
sum = 0
for right in range(mid + 1, high + 1):
sum = sum + A[right]
if sum > right_sum:
right_sum = sum
right_index = right
return left_index, right_index, left_sum + right_sum
def find_max_subarray(A, low, high):
"""
寻找数组中的最大子数组
:param A:
:param low:
:param high:
:return:
"""
if low == high:
return low, high, A[low]
else:
# 求中值
mid = (low + high) / 2
# 求左子数组最大子数组
left_low, left_high, left_sum = find_max_subarray(A, low, mid)
# 求右子数组最大子数组
right_low, right_high, right_sum = find_max_subarray(A, mid + 1, high)
# 求跨两个子数组的最大子数组
cross_low, cross_high, cross_sum = find_max_crossing_subarray(A, low, mid, high)
# 选出最大子数组
if left_sum >= right_sum and left_sum >= cross_sum:
return left_low, left_high, left_sum
elif right_sum >= left_sum and right_sum >= cross_sum:
return right_low, right_high, right_sum
elif cross_sum >= left_sum and cross_sum >= right_sum:
return cross_low, cross_high, cross_sum
if __name__ == "__main__":
random_list = [random.randint(-100, 100) for _ in range(100)]
print random_list
alow, ahigh, asum = find_max_subarray(random_list, 0, len(random_list) - 1)
print random_list[alow: ahigh + 1], asum
|
