Балансировка (нужно оптимизировать код)

Question

Есть задача, нужно отбалансировать список чисел так, чтобы в итоге вывело минимальную абсолютную разницу. Нужно ускорить , чтобы можно было быстро посчитать до 10^6 входных чисел.

Входные данные:
n = количество чисел
Количество чисел до n

Пример входа:
6
1 2 3 4 5 6
Выход:
0
Потому что 1 + 2 + 3 + 4 - 5 - 6
Минимальная абсолютная разница = 0

Мой код:

n = int(input())
list_of_nums = list(map(int,input().split()))
minim = 9999999999
for i in range(len(list_of_nums)):
    tmp = abs( sum(list_of_nums[i + 1:]) - sum(list_of_nums[:i+1]) )
    if tmp < minim:
        minim = tmp
print(minim)

Answer 1

если взять ваш код за основу, то

вместо range(len(list_of_nums)) надо все таки проходить range(1, len(list_of_nums) - 1)
ваш код из-за вычисления сумм имеет сложность O(n^2), хотя можно уложиться в O(n):

например чтобы получать суммы не надо считать сумму всех элементов слева и справа от i, а достаточно увеличивать и уменьшать суммы на один элемент

кстати это позволяет избавиться от вашего узкого места с minim = 9999999999, ведь можно предложить список чисел, значительно больших 9999999999

код:

left = sum(arr[:1])
right = sum(arr[1:])
minim = abs(left - right)

for i in range(1, len(arr) - 1):
    left += arr[i]
    right -= arr[i]
 
    tmp = abs(left - right)
    if tmp < minim:
        minim = tmp

print(minim)

по идее можно попробовать оптимизировать abs, перейдя к квадратам, но, честно говоря, я не знаю что быстрее, если abs делается через if, тогда работа с квадратами быстрее, если через сброс бита знака, то abs быстрее

БЛОГ НА HUSL

Балансировка (нужно оптимизировать код)

Ответы (1 шт):