假设有一个数组,为[1, 2, -3, 4, -2, 5, -3, -1, 7, 4, -6],如何找它元素和最大的子数组呢?
答案是[4, -2, 5, -3, -1, 7, 4],元素和为14.
分析:
带记忆的递归,逐步记录求和:
a = [1, 2, -3, 4, -2, 5, -3, -1, 7, 4, -6]
n = len(a)-1
record = [0]*(n+1)
record[0] = 1
for i in range(1, n+1): # 用下标1~n来储存n个数
record[i] = record[i-1] + a[i] # 用record记录a[i]前i个的和
max_num = 0
max_list = []
for i in range(1, n+1):
for j in range(0, i):
sums = record[i] - record[j] # 这样求sum
if (sums > max_num):
max_num = sums
max_list.append(max_num)
print(max(max_list))
其中record的记录是:
>>> record
[1, 3, 0, 4, 2, 7, 4, 3, 10, 14, 8]