Как сильно include нагружает сервер?

Это большое заблуждение - файловые операции очень быстрые на самом деле, потому что чаще всего то, что вы считаете файловой операцией таковой на самом деле не является. Например include скорее всего вообще не будут трогать ваш диск при многократном повторении, так как файлы, доступ к которым осуществляется многократно, вероятнее всего окажутся в дисковом буфере RAM и скорость доступа к ним будет выше чем доступ к БД и даже ко всяким всеми любимым NoSQL, которые часто заявляются как самые быстрые хранилища.
На самом деле надо пробовать в каждой конкретной ситуации, и файлы не редко окажутся в выигрыше.

Как максимизировать сумму элементов выбираемых из списка?

xmoonlight, он не линеен, насколько я понимаю.
Как вы правильно заметили у него сложность (log n)

Как максимизировать сумму элементов выбираемых из списка?

xmoonlight, там обсуждают четный поиск минимум в скользящем окне.
В видео Елена говорит как раз что это действительно сложно O(n²) и описывает читерский вариант со стэком.

Как перенести дамп базы из MariaDB в MySQL?

Через phpmyadmin сработало. А какая разница - там же внутри тот же mysqldump?

Как максимизировать сумму элементов выбираемых из списка?

xmoonlight, очевдино с момента когда график функции перестает быть прямой линией.
Даже 100500*n+800000000 - это уравнение прямой, а значит и сложность линейная

(n/2)*n - это какая сложность?

O(n²)

Как максимизировать сумму элементов выбираемых из списка?

xmoonlight, на самом деле то же самое только максимума и окно скользит в обратном направлении. Это кстати её же задача ;)

2n - это линейная сложность.

Как максимизировать сумму элементов выбираемых из списка?

Вот тут объясняется идея https://www.youtube.com/watch?v=NJ1wZUJwke8&featur...

Предыдущие видео на которые она ссылается (для понимания предыдущего видео необязательны):
https://www.youtube.com/watch?v=jkMF8s4qI_M&featur...
https://www.youtube.com/watch?time_continue=3&v=WM...

Как максимизировать сумму элементов выбираемых из списка?

это k-кратный, кмк...

Это и есть O(n)

ещё же есть итерирование на каждом шаге именно внутри тела цикла нескольких элементов в зависимости от входного параметра:

Там работы с деком и если присмотреться то станет понятно, что каждый элемент последовательности в худшем случае будет помещён в дек не более одного раза и не более одного раза покинет дэк.
Соотвественно это все равно O(n)

Как максимизировать сумму элементов выбираемых из списка?

xmoonlight, нет - эти алгоритмы линейные.
Точнее в первом листинге https://ideone.com/ZU8Mrr на самом деле есть неленейность (насколько я его могу понять), но она скрыта внутри встроенных функций, а не в самом алгоритме.
Если мы возмём понятный мне аналог на питоне, который есть ниже, то там есть функция max() которая не линейная. Это так.
Но последняя реализация моя линейная так как max убрана и заменена поиск максимума на деке.

Линейный - это когда в худшем случае количество любых смещений при переборе элементов списка не превышает количества элементов этого списка.

Не совсем. Если требуется k*n смещений где k - константа - это всё равно линейный алгоритм.
Т.е. если мне надо всего 2 прохода (или 3, как здесь, но можно свести к 2) по массиву не зависимо от его длины, т.е. всегда 2. То алгоритм остается линейным.

Как максимизировать сумму элементов выбираемых из списка?

xmoonlight, про какой листинг речь?
https://pastebin.com/jEWsBThL
Это O(n), но никак не логорифм

Как максимизировать сумму элементов выбираемых из списка?

xmoonlight, в ветке отмеченyой ответом решение. Сложность O(n)

Как максимизировать сумму элементов выбираемых из списка?

dmshar, решение есть. Обсуждение в ветке ответа Роман Румянцев (там же объяснение нюансов итогового кода)
Ссылка на итоговый код: https://pastebin.com/jEWsBThL

Как максимизировать сумму элементов выбираемых из списка?

Роман Румянцев, добавляем скорости богу функциональности: https://pastebin.com/jEWsBThL
Довел ваше решение - теперь никакого max в цикле - для поиска максимума используем дек.
Правда дек самописный.
Это по двум причинам:
1 Я показывал дочери как реализовать дек вообще и как сделать его быстрым игонрируя расход памяти.
2 Я просто ничего не знал про модуль collections :\

Задача решена и сдана. Интересно что в целом (не эта последняя часть) решение поулчилось оч. многословное (я вижу где у неё проблемы и можно убрать один лишний прогон), но в сети гуглятся решения, которые сделаны вообще за один единственный прогон и люди жалуются что решения эти не проходят по времени...

Главный вывод - задач всё же решается за линейное время. Огромное спасибо за помощь.

Как максимизировать сумму элементов выбираемых из списка?

Алгоритм не будет линейным. Здесь O(n^2), как мне кажется.

Как максимизировать сумму элементов выбираемых из списка?

Роман Румянцев, спасибо за реализацию - познакомился с лямбдами (пришлось звать дочь для объяснения).
Кстати как минимум в пайтоновской реализации есть проблемка, из-за которого в результат могут попадать элемент за пределами списка. Вместо if next < 0 нужно использовать if next < 0 or next > len(data):

Но увы - программа теперь не проходит по скорости - сыплетася на больших k - всё из-за max() для скользящего отрезка. Попробую избавится от этого недостастака

Как максимизировать сумму элементов выбираемых из списка?

Роман Румянцев, нашёл как минимум одну ошибку в коде который описал выше - проблема была тут:

тут может быть выход за границы массива, это надо учесть

Я это сделал оригинальным образом - нарастил массив maxDef содержащий максимумы в окнах последним элементом, что конечно не правильно - правильным было нарастить исходный массив k-1 нулем, чтобы создать последнее псевдоокно, состоящее из 1 последнего элемента и нолей свисающих за край массива.

Внес изменения: https://pastebin.com/kq6kV4hZ

Но всё равно ошибка где-то в реализации последнего блока. На таком наборе выдает очевидно невернный результат:

8 3
1 2 3 4 1 6 7 8 1 1 9 11 7 14
minA: [1, 2, 1, 1, 1, 6, 1, 1, 1, 1, 7, 7]
defA: [6, 18, 8, 11, 14, 126, 16, 10, 11, 21, 189, 224, 0, 0]
defA: [6, 18, 8, 11, 14, 126, 16, 10, 11, 21, 189, 224, 0, 0]
maxDef: [1, 1, 4, 5, 5, 5, 6, 9, 10, 11, 11, 11]
best next: [5, 5, 5, 6, 9, 10, 11, 11, 11]
summ: [356, 368, 358, 251, 238, 350, 240, 234, 235, 224, 224, 224]
start chain: 1

Вместно 224 в конечном блоке максимум == 189

Завтра буду продолжать. Но ваша идея работает, я полагаю. Проблема в реализации.

Как максимизировать сумму элементов выбираемых из списка?

Роман Румянцев, спасибо, но я уже сам размотал вашу идею. Это похоже на решение, и на тестовых данных у меня работает. Но не проходит онлайн проверку, не понятно на каком наборе данных :(

https://pastebin.com/UNK772g0 - вот реализация всей задачи. Конкретно вынесенное в вопрос сюда это блок начиная с
# =========================================================================================

Вот запуск на тестовых данных и промежуточные результаты:

def: [6, 18, 8, 11, 14, 126]
maxDef: [1, 1, 4, 5, 5, 5, 5]
best next: [5, 5, 5]
summ: [132, 144, 134, 126, 126, 126]

Здесь:
def - просматриваемый массив
maxDef - индекс максимум в скользящем окне 3, для окна начинающегося в i

best next и summ - то что вы называете кэшем:
Первый содержит индекс наиболее подходящего элемента для элемента i
второй собственно суммы.

Если интересно вся задача здесь: https://informatics.mccme.ru/moodle/mod/statements...
Правда решаем на Python и дочка только учит, а для меня язык не родной, поэтому наверно что-то в реализации может быть коряво написано - прошу простить за такое.

Сейчас пробую составить свои наборы данных и потестить ещё

Как максимизировать сумму элементов выбираемых из списка?

Похоже ваш код работает, но я по правде говоря не могу въехать в реализацию.

Последние k элементов заносятся в кэш как есть, от них никуда не деться.

В какой кэш? Что он нам даёт? Как мы его используем и почему последние k элементов должны попасть туда в начале?

Далее для каждого элемента с номером i нужно просмотреть, как он сочетается с элементами i + k .. i + 2k

Вы имеете ввиду найти в диапазоне от i+k до i+2k наилучшую для него пару? И что? Записать для этого элемента индекс наилучшей пары? Предположим.

И так идём до первого элемента. Потом выбираем лучший из элементов с номерами 1 .. k

А почему я тогда не могу начать с начала и выбрав максимум на отрезке 1..k подбирать наилучшую пару для него? На отрезке k..2k?
В смысле чем такой подход отличается от вашего предложения не могу уловить...

Но реализовывать пошёл - попробую.

Как максимизировать сумму элементов выбираемых из списка?

uvelichitel,

в один проход?

Не факт, что в один. Там у меня до этого еще несколько вычислений, которые уже делают 3 прохода, но там всегда три прохода (можно свести к двум, но сейчас не это важно) и от n не зависит.

храня промежуточные результаты в матрице и оптимизируя очередью или стеком.

Возможно деком - уже дек активно юзаю чтобы свести задачу к этой.

Как максимизировать сумму элементов выбираемых из списка?

dmshar,

Я имел ввиду, на ограничения количества элементов, из которых составляется сумма. Если нет - то все очень не радужно. Метод "ветвей и границ" точного решения не гарантирует.

Нет - ограничения нет. Количество элементов может быть любым.

Надеюсь, про O(n) это вы пошутили.

Я серьёзен как никогда - с этой задачей пришла дочь, а я не могу справится. Задача из раздела который называется "Линейные алгоритмы", что как бы намекает.
На самом деле задачка там сильно посложнее, но в итоге легко за линейное время сводится вот этой и дальше понять не могу чего делать.