最大子数组--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. 动态规划法:


个人认为其中的难点: 计算前 n 项和,这是一个前缀,判断只要前缀是大于零的那么加上后一位就是越来越大的。一直向后相加 就可以了。


一旦前缀小于零,就是说前 n 项和小于零了。那么那个前缀形成的子数组不可能在变大,所以要开始新 的前缀(新的子数组)。


# 动态规划法求最大子数组
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))










分享给朋友:
您可能感兴趣的文章:
随机阅读: