使用分治法解决最大子数组问题的Python程序

使用分治法解决最大子数组问题的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 ‘实现的,它帮助计算每个子数组的和。

  • 在方法外,定义了一个列表,并在控制台上显示。

  • 确定列表的长度。

  • 通过传递此列表调用计算子数组和的方法。

  • 将结果输出到控制台。

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程