Алгоритм Кадане для минимальной по модулю суммы подмассива

Question

не могли бы мне подсказать как применить алгоритм Кадане для поиска непрерывного подмассива с минимальной по модулю суммой. Мой код, до введения в него модулей находил отрезок с минимальной суммой, т.е. с учетом знаков. После введения abs не удается заставить его работать. Получается заставить работать на конкретном примере, но это скорее подгонка под ответ.

#a =[2, 2, 3, -15, 2, -3, -12, 2, 3] 
a = [2,2,6,3,2,7,12,-9,10,10] 
#a =[2,2,6,-2,-3,7,12,-9] 
res = a[0] 
res_index_l = 0 
res_index_r = 0 
sum = 0 
pos = 0
for r in range(len (a)):
    if abs(sum + a[r]) < abs(a[r]):
        sum = sum + a[r] 
    else:
        sum = a[r]
        pos = r
    if abs(sum) < abs(res): 
        res = sum 
        res_index_l = pos 
        res_index_r = r 
print (res, a[res_index_l:res_index_r+1])

Answer 1

Можно сочинить O(nlogn) алгоритм:

Посчитать кумулятивные (префиксные) суммы массива, т.е.

C[0] = A[0]
for i in range(1, len(A)):
   С[i] = C[i-1] + A[i]

Отсортировать их, и найти минимальную разницу между соседями - это и есть минимальная по модулю сумма подмассива

БЛОГ НА HUSL

Алгоритм Кадане для минимальной по модулю суммы подмассива

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