РЕДАКТИРОВАТЬ: Я полагаю, что решение всех сумм на самом деле огромная работа впустую. Это интересно только если m >> n. Еще вот мое решение.
Представьте себе гонку между зайцем и черепахой. Я надеюсь, что вы знаете эту историю ...
Таким образом, Заяц "я" позволяет черепахе "J" идти первым. Он знает, что он быстрее и что он может вздремнуть. Он беспокоится, только если Черепаха скрыта из виду, «Т» метров дальше, затем он очень быстро бежит, пока не увидит Черепаху и снова не заснет ... И так далее.
Итак, инициализация
i = 0
j = 0
bestval = inf
index = none
diff = T
Основной цикл
while(true):
if diff < 0:
i++
diff += A[i]
elif j==n:
break
else:
j++
diff += A[j]
# record best distance
if abs(diff) < bestval:
bestval = diff
index = (i, j)
Вы не можете пропустить оптимальное, потому что вы не расширяете исследования в направлениях, увеличивающих abs (diff). Бессмысленно продолжать суммировать числа, если у вас уже слишком много ...
Таким образом, вы выполняете только два прохода на A с обоими j и i, один раз для каждого T. Это должно быть O (mn). Вы даже можете разорвать цикл, если diff = 0.