3/ Наиболее оптимальное решение через префиксные суммы (асимптотика O(N)).
Пусть S – сумма всех пакетов, Si- - префиксная сумма всех пакетов до i невключительно, Si+ - префиксная сумма всех пакетов после i, включая i, Spi- – сумма пакетов до i, Spi+ - сумма пакетов после i.
Тогда:
Si+ = S – Si-
Spi- = Sp(i-1)- + Si-
Spi+ = Sp(i-1)+ - Si+ = Sp(i-1)+ – S + Si-
Получаем:
f(i) = Spi- + Spi+ = Spi- + Spi+ + 2Si- - S = f(i-1) + 2Si- - S
Учитывая, что f(i) – парабола с ветвями вверх, то нам нужно найти такие Si- и S, что выполняется:
2S(i – 1)- < S и 2Si- >= S одновременно.
Итого нам надо искать первое i такое, что 2Si- >= S