Khi cần tìm mảng con tối đa bằng thuật toán Kadane, một phương pháp được xác định để giúp tìm mảng con tối đa. Trình lặp được sử dụng để theo dõi mảng con tối đa.
Dưới đây là minh chứng về điều tương tự -
Ví dụ
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)) Đầu ra
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.
Giải thích
-
Phương thức có tên ‘find_max_sub_array’ được xác định có ba tham số.
-
Mảng con tối đa trong một phạm vi nhất định được tìm thấy.
-
Nó trả về một bộ giá trị trong đó các chỉ số bên trái, bên phải của mảng con tối đa được trả về cùng với tổng của nó.
-
Một vòng lặp được sử dụng để kiểm tra mảng phụ tối đa kết thúc ở chỉ mục i.
-
Đây là mức tối đa của tất cả các mảng con.
-
Phương thức này cũng theo dõi tổng tối đa của mảng con được thấy cho đến bây giờ, khi vòng lặp lặp qua các chỉ số bên trái và bên phải.
-
Bên ngoài phương thức, danh sách các số được người dùng lấy làm đầu vào.
-
Đây là một tham số cho phương thức.
-
Nó được hiển thị dưới dạng đầu ra trên bảng điều khiển.