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'라는 메서드가 정의되어 있습니다.
-
주어진 범위 내에서 최대 하위 배열을 찾았습니다.
-
최대 하위 배열의 왼쪽, 오른쪽 인덱스가 합과 함께 반환되는 튜플을 반환합니다.
-
루프는 인덱스 i에서 끝나는 최대 하위 배열을 확인하는 데 사용됩니다.
-
모든 하위 배열의 최대값입니다.
-
또한 이 메서드는 루프가 왼쪽 및 오른쪽 인덱스를 반복하므로 지금까지 본 하위 배열의 최대 합계를 추적합니다.
-
메소드 외부에서 숫자 목록은 사용자가 입력한 것으로 간주됩니다.
-
이것은 메소드에 매개변수로 전달됩니다.
-
콘솔에 출력으로 표시됩니다.