Там есть массивA содержащие (положительные и отрицательные) целые числа. Найдите (непрерывный) подмассив, абсолютная сумма элементов которого минимальна, например:

A = [2, -4, 6, -3, 9]
|(−4) + 6 + (−3)| = 1 <- minimal absolute sum

Я начал с реализации алгоритма грубой силы, который былO(N^2) или жеO(N^3)Хотя это дало правильные результаты. Но задача уточняет:

complexity:
- expected worst-case time complexity is O(N*log(N))
- expected worst-case space complexity is O(N)

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

Мой вопрос - правильный ли алгоритм алгоритма Кадане? Если нет, не могли бы вы указать мне правильное направление (или назвать алгоритм, который мог бы помочь мне здесь)? Я не хочу готовый код, мне просто нужна помощь в поиске правильного алгоритма.