যখন ডিভাইড এন্ড কনকর মেথড ব্যবহার করে ম্যাক্সিমাম সাবঅ্যারে প্রাব্লেম সমাধান করতে হয়,
নিচে এর демонস্ট্রেশন দেওয়া হলো:
উদাহরণ
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’ মেথড ব্যবহার করে অর্জিত হয় যা প্রতিটি সাব অ্যারের যোগফল গণনা করতে সাহায্য করে।
মেথডের বাইরে একটি লিস্ট ডিফাইন করা হয়েছে, এবং কনসোলে প্রদর্শিত হয়েছে।
লিস্টের দৈর্ঘ্য নির্ধারণ করা হয়েছে।
সাব অ্যারের যোগফল গণনা করার মেথডটি এই লিস্ট পাস করে কল করা হয়েছে।
যোগফল আউটপুট হিসেবে কনসোলে প্রদর্শিত হয়েছে।
