使用 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处结束的最大子数组。
这是所有子数组的最大值。
该方法还跟踪直到现在看到的子数组的最大和，因为循环遍历左右索引。
在该方法之外，用户将数字列表作为输入。
这作为参数传递给方法。
它在控制台上显示为输出。