[算法] 求数组的子数组之和的最大值
相关文章:
书籍:
《编程珠玑(第2版)》第8章 算法设计技术 —— 还是这本书讲得全面点好些. 很多问题还没搞明白, 还得看.
《编程之美》2.14 求数组的子数组之和的最大值
题目描述:
输入一个整形数组, 数组里有正数也有负数. 数组中连续的一个或多个整数组成一个子数组, 每个子数组都有一个和. 求所有子数组的和的最大值.
例子: [1, -2, 3, 5, -3, 2] 返回: 8 [0, -2, 3, 5, -1, 2] 返回: 9 [-9, -2, -3, -5, -3] 返回: -2
扩展问题2: 返回了最大子数组的位置(均有返回)
N^3的方法就不写了, 我都想不出这种方法...
解法一, n^2
def find_maximum_subarray(A):
max = -float("inf")
low = high = 0
for i in range(0, len(A)):
sum = 0
for j in range(i, len(A)):
sum += A[j]
if sum > max:
max = sum
low = i
high = j
return (low, high, max)
解法二, 分治方法 nlgn
主要思想: 采用二分策略, 将序列分成左右两份. 那么最长子序列有三种可能出现的情况, 即
- 只出现在左部分.
- 只出现在右部分.
- 出现在中间, 同时涉及到左右两部分.
分情况讨论之.
def find_max_crossing_subarray(A, low, mid, high):
left_sum = -float('inf')
sum = 0
for i in range(mid, low - 1, -1):
sum = sum + A[i]
if sum > left_sum:
left_sum = sum
max_left = i
right_sum = -float('inf')
sum = 0
for j in range(mid + 1, high + 1):
sum = sum + A[j]
if sum > right_sum:
right_sum = sum
max_right = j
return (max_left, max_right, left_sum + right_sum)
def find_maximum_subarray(A, low, high):
if high == low:
return (low, high, A[low])
else:
mid = (low + high) / 2
(left_low, left_high, left_sum) = find_maximum_subarray(A, low, mid)
(right_low, right_high, right_sum) = find_maximum_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)
else:
return (cross_low, cross_high, cross_sum)
解法三, 线性时间 n
从头遍历数组元素, 并累加求和, 如果和小于0就自当前元素从新开始, 否则就一直累加, 取其中最大值便为解.
#-*-coding:utf-8-*-
def find_maximum_subarray(A):
max_so_far = max_ending_here = A[0]
high = low = 0
for i in range(1, len(A)):
# max_ending_here = max(A[i], max_ending_here + A[i])
# max_so_far = max(max_so_far, max_ending_here)
if max_ending_here < 0:
max_ending_here = A[i]
t_low = i # 记录当前的起始位置
else:
max_ending_here += A[i]
if max_ending_here > max_so_far:
max_so_far = max_ending_here
low, high = t_low, i # 记录并更新最大子数组位置
print(low, high, max_so_far)
return max_so_far
过程:
[13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
max_ending_here: 13 10 -15 20 17 1 -22 18 38 31 43 38 16 31 27 34
max_so_far : 13 13 13 20 20 20 20 20 38 38 43 43 43 43 43 43
扩展问题1:
这篇博文分析了书中的错误: http://www.ahathinking.com/archives/120.html
#-*-coding:utf-8-*-
# 不跨界的情况
def find_maximum_not_crossing_subarray(A):
max_so_far = max_ending_here = A[0]
for i in range(1, len(A)):
if max_ending_here < 0:
max_ending_here = A[i]
else:
max_ending_here += A[i]
if max_ending_here > max_so_far:
max_so_far = max_ending_here
return max_so_far
# 跨界的情况, 找最小, 剩下的就是最大的了
def find_maximum_crossing_subarray(A):
sum_A = min_so_far = min_ending_here = A[0]
for i in range(1, len(A)):
sum_A += A[i]
if min_ending_here > 0:
min_ending_here = A[i]
else:
min_ending_here += A[i]
if min_ending_here < min_so_far:
min_so_far = min_ending_here
return sum_A - min_so_far
def find_maximum_subarray(A):
max_not_crossing = find_maximum_not_crossing_subarray(A)
print('max_not_crossing: %d' % max_not_crossing)
if max_not_crossing < 0:
return max_not_crossing
max_crossing = find_maximum_crossing_subarray(A)
print('max_crossing: %d' % max_crossing)
if max_crossing > max_not_crossing:
return max_crossing
return max_not_crossing
if __name__ == "__main__":
# A = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
# A = [-1, -2, -3]
# A = [1, -2, 3, 5, -3, 2]
# A = [0, -2, 3, 5, -1, 2]
# A = [-9, -2, -3, -5, -3]
A = [8, -10, -1, 3, 60, -1, -6]
print(find_maximum_subarray(A))
扩展问题:
1、如果数组是二维数组, 同样要你求最大子数组的和列?
2、如果是要你求子数组的最大乘积列?
