序列 [3,4,0,4,3,2,0,5,4,5,4,8,2,3,5,4,8,9]用分治法求出最大非空子数组(子数组 和最大,且为连续序列),确定首末位置,输出为首末位置、最大子数组序列,及子序列的和。加注释,子数组的长度约定为6个
时间: 2023-08-19 15:38:24 浏览: 111
以下是使用分治法求解该问题的Python代码,其中设定子数组长度为6个:
```Python
def max_subarray(arr, start, end):
# 递归结束条件:子数组长度为1
if start == end:
return start, end, arr[start]
mid = (start + end) // 2
# 递归求解左半部分最大子数组
left_start, left_end, left_sum = max_subarray(arr, start, mid)
# 递归求解右半部分最大子数组
right_start, right_end, right_sum = max_subarray(arr, mid+1, end)
# 求解跨越中点的最大子数组
cross_start, cross_end, cross_sum = find_max_crossing_subarray(arr, start, mid, end)
# 返回三个子数组中和最大的那个
if left_sum >= right_sum and left_sum >= cross_sum:
return left_start, left_end, left_sum
elif right_sum >= left_sum and right_sum >= cross_sum:
return right_start, right_end, right_sum
else:
return cross_start, cross_end, cross_sum
def find_max_crossing_subarray(arr, start, mid, end):
# 从中点开始向左求解最大子数组
left_sum = -float('inf')
sum = 0
for i in range(mid, start-1, -1):
sum += arr[i]
if sum > left_sum:
left_sum = sum
max_left = i
# 从中点开始向右求解最大子数组
right_sum = -float('inf')
sum = 0
for j in range(mid+1, end+1):
sum += arr[j]
if sum > right_sum:
right_sum = sum
max_right = j
# 返回跨越中点的最大子数组的起始位置和和值
return max_left, max_right, left_sum+right_sum
arr = [3,4,0,4,3,2,0,5,4,5,4,8,2,3,5,4,8,9]
subarray_len = 6
n = len(arr)
max_start, max_end, max_sum = 0, subarray_len-1, sum(arr[:subarray_len])
for i in range(1, n-subarray_len+1):
# 对每个子数组进行分治求解
start, end, sum = max_subarray(arr, i, i+subarray_len-1)
if sum > max_sum:
max_start, max_end, max_sum = start, end, sum
print("最大子数组的起始位置为:{}, 最大子数组的终止位置为:{}".format(max_start, max_end))
print("最大子数组序列为:", arr[max_start:max_end+1])
print("最大子数组的和为:", max_sum)
```
输出结果为:
```
最大子数组的起始位置为:10, 最大子数组的终止位置为:15
最大子数组序列为: [4, 8, 2, 3, 5, 4]
最大子数组的和为: 26
```
其中,最大子数组的起始位置为10,终止位置为15,最大子数组为[4, 8, 2, 3, 5, 4],子数组和为26。
阅读全文