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」という名前のメソッドが定義されており、3つのパラメーターを取ります。

• 指定された範囲内の最大のサブ配列が見つかりました。

• 最大サブ配列の左右のインデックスがその合計とともに返されるタプルを返します。

• ループは、インデックスiで終わる最大のサブ配列をチェックするために使用されます。

• これは、すべてのサブアレイの最大値です。

• このメソッドは、ループが左右のインデックスを繰り返すため、これまでに見られたサブ配列の最大合計も追跡します。

• メソッドの外部では、番号のリストはユーザーによる入力として取得されます。

• これはパラメータとしてメソッドに渡されます。

• コンソールに出力として表示されます。