Divide and Conquer를 사용하여 최대 하위 배열 문제를 해결하는 Python 프로그램

분할 정복 방법을 사용하여 최대 하위 배열 문제를 해결해야 하는 경우

아래는 동일한 데모입니다 -

예

def max_crossing_sum(my_array, low, mid, high):

   sum_elements = 0
   sum_left_elements = -10000

   for i in range(mid, low-1, -1):
   sum_elements = sum_elements + my_array[i]

   if (sum_elements > sum_left_elements):
      sum_left_elements = sum_elements

   sum_elements = 0
   sum_right_elements = -1000
   for i in range(mid + 1, high + 1):
      sum_elements = sum_elements + my_array[i]

      if (sum_elements > sum_right_elements):
         sum_right_elements = sum_elements

   return max(sum_left_elements + sum_right_elements, sum_left_elements, sum_right_elements)

def max_sub_array_sum(my_array, low, high):

   if (low == high):
      return my_array[low]

   mid = (low + high) // 2

   return max(max_sub_array_sum(my_array, low, mid), max_sub_array_sum(my_array, mid+1, high), max_crossing_sum(my_array, low, mid, high))

my_list = [23, 12, 45, 67, 89, 11]
list_length = len(my_list)
print("The list is :")
print(my_list)

max_sum = max_sub_array_sum(my_list, 0, list_length-1)
print("The maximum contiguous sum is ")
print(max_sum)

출력

The list is :
[23, 12, 45, 67, 89, 11]
The maximum contiguous sum is
247

설명

• 목록의 왼쪽 부분에 있는 요소의 합을 계산하는 'max_crossing_sum'이라는 메서드가 정의되어 있습니다.

• 이것은 모든 하위 배열의 합을 계산하는 데 도움이 되는 'max_sub_array_sum'을 사용하여 달성됩니다.

• 메소드 외부에 목록이 정의되어 콘솔에 표시됩니다.

• 목록의 길이가 결정됩니다.

• 이 목록을 전달하여 하위 배열의 합을 계산하는 메서드를 호출합니다.

• 합계는 콘솔에 출력으로 표시됩니다.