Нахождение минимальной абсолютной суммы подмассива
Там есть массив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)
После некоторых поисков я подумал, что, возможно, алгоритм Кадане можно изменить для решения этой проблемы, но мне не удалось это сделать.
Мой вопрос - правильный ли алгоритм алгоритма Кадане? Если нет, не могли бы вы указать мне правильное направление (или назвать алгоритм, который мог бы помочь мне здесь)? Я не хочу готовый код, мне просто нужна помощь в поиске правильного алгоритма.