У меня есть массив A
содержит целые числа (положительные, отрицательные или ноль). Итак, я хочу получить максимальную абсолютную сумму диапазона (что-то вроде Kadane's algorithm
, но с абсолютным значением).
Например, пусть A будет:
A = [-3, 2 ,-3, 1]
так что ответ есть 4 как abs(A[0] + A[1] + A[2]) = 4.
Я пытался найти решение, используя алгоритм Кадане, поддерживающий текущую максимальную сумму, но в некоторых случаях, похоже, он не работает. Есть ли способ получить ответ?
Expected time complexity: O(n*log(n))
Задача ещё не решена.
Других решений пока нет …