values и список правок edits, где edits[i] = [pos, x].
Правки применяются по очереди: правка ставит values[pos] = x. После каждой правки посчитайте наибольшую сумму, которую можно набрать, выбирая элементы массива так, чтобы никакие два выбранных не стояли рядом. Можно не выбрать ни одного элемента — тогда сумма 0.
Верните сумму этих ответов по всем правкам по модулю 10⁹ + 7.
Пересчитывать всё заново после каждой правки слишком долго — нужно обновлять ответ быстрее, чем за O(n).values=[4, 2, 6, 3], edits=[[2, -1], [3, 8]] → 19
После первой правки массив [4, 2, -1, 3], лучше всего взять 4 и 3: 7. После второй — [4, 2, -1, 8], лучшее 4 + 8 = 12. Ответ 7 + 12 = 19.
values=[-2, -7], edits=[[1, -3]] → 0
Все числа отрицательные, выгоднее ничего не брать: сумма 0.
values=[5, 5, 5], edits=[[1, 20], [1, 1]] → 30
pos < len(values)x ≤ 10⁵values=[4, 2, 6, 3], edits=[[2, -1], [3, 8]]
19
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 88 тестов на сервере, включая скрытые.