0

не могли бы мне подсказать как применить алгоритм Кадане для поиска непрерывного подмассива с минимальной по модулю суммой. Мой код, до введения в него модулей находил отрезок с минимальной суммой, т.е. с учетом знаков. После введения 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])

1 ответ 1

2

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

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

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

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

2
  • Благодарю, в этом случае нам будет не важен знак суммы. 26 авг 2020 в 18:33
  • @Александр если ответ решает вопрос, поставьте галку слева от него
    – dIm0n
    26 авг 2020 в 18:36

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.