資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法學研究使用 Kadane 演算法求解最大子陣列問題的 Python 程式
當需要使用 Kadane 演算法查詢最大子陣列時，會定義一種有助於查詢子陣列最大值的方法。使用迭代器來跟蹤最大子陣列。
以下是該演算法的演示：
示例
def find_max_sub_array(my_list, beg, end):
max_end_at_i = max_seen_till_now = my_list[beg]
max_left_at_i = max_left_till_now = beg
max_right_till_now = beg + 1
for i in range(beg + 1, end):
if max_end_at_i > 0:
max_end_at_i += my_list[i]
else:
max_end_at_i = my_list[i]
max_left_at_i = i
if max_end_at_i > max_seen_till_now:
max_seen_till_now = max_end_at_i
max_left_till_now = max_left_at_i
max_right_till_now = i + 1
return max_left_till_now, max_right_till_now, max_seen_till_now
my_list = input('Enter the list of numbers... ')
my_list = my_list.split()
my_list = [int(x) for x in my_list]
beg, end, max_val = find_max_sub_array(my_list, 0, len(my_list))
print('The maximum subarray begins at index {}, ends at index {}'
' and its sum is {}.'.format(beg, end - 1, max_val))輸出
Enter the list of numbers... 2 5 7 12 6 8 The maximum subarray begins at index 0, ends at index 5 and its sum is 40.
說明
定義了一個名為“find_max_sub_array”的方法，它接受三個引數。
計算特定範圍內的最大子陣列。
返回一個元組，其中最大子陣列的左右索引及其總和將返回。
使用迴圈來檢查以索引 i 結尾的最大子陣列。
這是所有子陣列的最大值。
該方法還會跟蹤到目前為止看到過的子陣列的最大總和，因為迴圈會迭代左右索引。
在方法之外，由使用者輸入數字列表。
將其作為引數傳遞給該方法。
將其顯示為控制檯上的輸出。
更新於：2021 年 4 月 17 日
216 次觀看
廣告