使用分而治之的 Python 程序解决最大子阵列问题
当需要使用分治法求解最大子阵列问题时,
以下是相同的演示-
示例
def max_crossing_sum(my_array, low, mid, high): sum_elements = 0 sum_left_elements = -10000 for i in range(mid, low-1, -1): sum_elements = sum_elements + my_array[i] if (sum_elements > sum_left_elements): sum_left_elements = sum_elements sum_elements = 0 sum_right_elements = -1000 for i in range(mid + 1, high + 1): sum_elements = sum_elements + my_array[i] if (sum_elements > sum_right_elements): sum_right_elements = sum_elements return max(sum_left_elements + sum_right_elements, sum_left_elements, sum_right_elements) def max_sub_array_sum(my_array, low, high): if (low == high): return my_array[low] mid = (low + high) //2 return max(max_sub_array_sum(my_array, low, mid), max_sub_array_sum(my_array, mid+1, high), max_crossing_sum(my_array, low, mid, high)) my_list = [23, 12, 45, 67, 89, 11] list_length = len(my_list) print("名单是:") print(my_list) max_sum = max_sub_array_sum(my_list, 0, list_length-1) print("最大连续和是 ") print(max_sum)输出结果
名单是: [23, 12, 45, 67, 89, 11] 最大连续和是 247
解释
定义了一个名为“max_crossing_sum”的方法,用于计算列表左侧元素的总和。
这是使用“max_sub_array_sum”来实现的,它有助于计算每个子数组的总和。
在方法之外,定义了一个列表,并显示在控制台上。
列表的长度是确定的。
通过传递这个列表来调用计算子数组和的方法。
总和在控制台上显示为输出