假设有一个数组,为[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)-1record = [0]*(n+1)record[0] = 1for i in range(1, n+1): # 用下标1~n来储存n个数record[i] = record[i-1] + a[i] # 用record记录a[i]前i个的和max_num = 0max_list = []for i in range(1, n+1):for j in range(0, i):sums = record[i] - record[j] # 这样求sumif (sums > max_num):max_num = sumsmax_list.append(max_num)print(max(max_list))
其中record的记录是:
>>> record[1, 3, 0, 4, 2, 7, 4, 3, 10, 14, 8]
