เมื่อต้องการค้นหาอาร์เรย์ย่อยสูงสุดโดยใช้อัลกอริทึมของ 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' ที่รับพารามิเตอร์สามตัว
-
พบอาร์เรย์ย่อยสูงสุดภายในช่วงที่กำหนด
-
ส่งคืน tuple โดยที่ดัชนีด้านซ้ายและด้านขวาของอาร์เรย์ย่อยสูงสุดจะถูกส่งกลับพร้อมกับผลรวม
-
ลูปใช้เพื่อตรวจสอบอาร์เรย์ย่อยสูงสุดที่สิ้นสุดที่ดัชนี i
-
นี่คือค่าสูงสุดของอาร์เรย์ย่อยทั้งหมด
-
วิธีการนี้ยังติดตามผลรวมสูงสุดของอาร์เรย์ย่อยที่มองเห็นได้จนถึงขณะนี้ เนื่องจากลูปวนซ้ำผ่านดัชนีด้านซ้ายและขวา
-
นอกวิธีการ รายการตัวเลขจะถูกนำมาเป็นอินพุตโดยผู้ใช้
-
สิ่งนี้ถูกส่งผ่านเป็นพารามิเตอร์ไปยังเมธอด
-
จะแสดงเป็นเอาต์พุตบนคอนโซล
