# 最大子数组--python实现

1. 暴力法：计算每一个 子数组 的和，选出最大的。时间复杂度O（n**3）

# -*-coding:utf-8 -*-
#暴力法求最大子数组
def max_child(arr):
max = 0
x = 0
y = 0
n = len(arr)
for i in range(0,n):
for j in range(i,n):
arr_sum = 0
for k in range(i,j+1):
arr_sum = arr_sum + arr[k]
# print(i,j,arr_sum)
if arr_sum > max :
max = arr_sum
x = i
y = j
print("最大子数组的起始-结束下标", x, y)
return max
arr = [1,2,3,4,5]
print("最大子数组的和：", max_child(arr))
2. 递归法：

# 注释掉的都是调试代码。

# 递归法求最大子数组
def max_child(arr, low, heigh):
if low == heigh:
return arr[low]
mid = (heigh + low) // 2
# print("mid:" ,mid)
m1 = max_child(arr, low, mid)
# print("m1:", m1)
m2 = max_child(arr, mid+1, heigh)
# print("m2:", m2)
now_left = arr[mid]
left = arr[mid]
for i in range(mid-1, low-1, -1):
now_left = now_left + arr[i]
if now_left > left:
left = now_left
now_right = arr[mid + 1]
right = arr[mid + 1]
for j in range(mid + 2, heigh+1):
now_right = now_right + arr[j]
if now_right > right:
right = now_right
m3 = left + right
# print("m3:", m3)
result = max(m1, m2, m3)
return resultarr = [1,2,3,4,5]
print(max_child(arr, 0, len(arr)-1)) 3. 动态规划法：

# 动态规划法求最大子数组
def max_child(arr):
result = arr[0]
sum = arr[0]
x = 0
for i in range(1, len(arr)):
if sum > 0:
sum += arr[i]
else:
sum = arr[i]
x = i
if sum > result:
result = sum
y = i
print("最大子数组的起始-结束下标", x, y)
return result
arr = [1, 2, -3, 4, 5]
print("最大子数组的和：",max_child(arr))