資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時裝研究
法律研究使用分治法解決最大子陣列問題的 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("The list is :")
print(my_list)
max_sum = max_sub_array_sum(my_list, 0, list_length-1)
print("The maximum contiguous sum is ")
print(max_sum)輸出
The list is : [23, 12, 45, 67, 89, 11] The maximum contiguous sum is 247
說明
定義了一個名為“max_crossing_sum”的方法，它計算列表中左側元素的總和。
這是使用“max_sub_array_sum”實現的，它有助於計算每個子陣列的總和。
在方法外，定義了一個列表並將其顯示在控制檯上。
確定列表的長度。
透過傳遞此列表來呼叫計算子陣列總和的方法。
該總和作為輸出顯示在控制檯上
更新於： 19-04-2021
328 次瀏覽
廣告