使用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('输入数字列表... ')
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('最大子阵列从索引{}开始，到索引{}结束，其中的总和是{}。'.format(beg, end - 1, max_val))

输出

输入数字列表... 2 5 7 12 6 8
最大子阵列从索引0开始，到索引5结束，其中的总和为40。

解释

• 定义了一个名为’find_max_sub_array’的方法，该方法需要三个参数。

• 求出给定范围内的最大子数组。

• 它返回一个元组，其中左、右指数的最大子阵列返回以及它的和。

• 使用循环来检查索引i下的具有最大子阵列。

• 这是所有子数组中的最大值。

• 该方法还在循环通过左和右指数时跟踪到目前为止所看到的子阵列的最大总和。

• 在外部，用户输入数字列表。

• 这被作为参数传递给该方法。

• 它在控制台上显示为输出。