Крис не дает ответа в списке [9,10,9], получая 10 вместо 9 + 9 = 18.
Джо не совсем прав. Торговый продавец требует, чтобы вы посетили каждый город, в то время как аналога здесь нет.
Одним из возможных решений будет рекурсивное решение:
function Max_route(A)
if A's length = 1
A[0]
else
maximum of
A[0]+Max_route(A[2...])
Max_route[1...]
У него та же функция big-O, что и у простой функции Фибоначчи, и она должна уступать некоторым из тех же оптимизаций (например, запоминание), если вы заботитесь об эффективности в дополнение к простому получению правильного ответа.
- MarkusQ
[Редактировать] ---
Поскольку некоторые люди, кажется, не понимают этого, я хочу объяснить, что я имел в виду под памяткой и почему это важно.
Вы можете обернуть вышеописанную функцию так, чтобы она вычисляла значение для каждого массива только один раз (при первом вызове) и при последующих вызовах просто возвращала сохраненный результат. Это заняло бы пространство O (n), но вернулось бы за постоянное время. Это означает, что весь алгоритм вернется за время O (n), лучше, чем экспоненциальное время менее загруженной версии выше. Я предполагал, что это было хорошо понято.
[Второе редактирование] ------------------------------
Если мы немного расширим вышеперечисленное и разделим его на части, мы получим:
f [] :- [],0
f [x] :- [x],x
f [a,b] :- if a > b then [a],a else [b],b
f [a,b,t] :-
ft = f t
fbt = f [b|t]
if a + ft.sum > fbt.sum
[a|ft.path],a+ft.sum
else
fbt
Который мы можем развернуть в псевдоосновное, используя только массивы n целых и логических чисел размера n, а также операции 1) индексация массива и присвоение индексированного массива, 2) математика целых чисел, включая сравнение, 3) if / then / else, и 4) один единственный цикл O (n):
dim max_sum_for_initial[n],next_to_get_max_of_initial[n],use_last_of_initial[n]
max_sum_for_initial[0] = 0
next_to_get_max_of_initial[0] = -1
use_last_of_initial[0] = false
max_sum_for_initial[1] = a[0]
next_to_get_max_of_initial[1] = -1
use_last_of_initial[1] = true
if a[0] > a[1]
max_sum_for_initial[2] = a[0]
next_to_get_max_of_initial[2] = 0
use_last_of_initial[2] = false
else
max_sum_for_initial[2] = a[1]
next_to_get_max_of_initial[1] = -1
use_last_of_initial[2] = true
for i from 3 to n
if a[i]+max_sum_for_initial[i-2] > max_sum_for_initial[i-1]
max_sum_for_initial[i] = a[i]+max_sum_for_initial[i-2]
next_to_get_max_of_initial[i] = i-2
use_last_of_initial[i] = true
else
max_sum_for_initial[i] = max+sum_for_initial[i-1]
next_to_get_max_of_initial[i] = i-1
use_last_of_initial[i] = false
В конце мы можем извлечь результаты (в обратном порядке):
for i = n; i >= 0; i = next_to_get_max_of_initial[i]
if use_last_of_initial[i] then print a[i]
Обратите внимание, что то, что мы только что сделали вручную, это то, что хороший компилятор для современного языка должен уметь выполнять с помощью хвостовой рекурсии, запоминания и т. Д.
Надеюсь, это достаточно ясно.
- MarkusQ
Это O (n).