数据结构
网络
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 次观看
广告