Дана последовательность (массив) целых чисел. Числа могут быть как отрицательные так и положительные. Предложите самый быстрый алгоритм поиска наибольшей суммы непрерывной последовательности.
Ответ
array = list( map( int, raw_input().split() ) ) max_sum = [ 0, ] for x in array: tmp = max_sum[ -1 ] + x if tmp < 0: tmp = 0 max_sum.append( tmp ) print max( max_sum ) http://ideone.com/y3Nwd Соблюдается условие, что последовательность может быть пуста. Работает за O(n).
Комментариев нет:
Отправить комментарий