Há uma matrizA contendo inteiros (positivos e negativos). Encontre um subarray (contíguo) cuja soma absoluta dos elementos seja mínima, por exemplo:

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

Comecei implementando um algoritmo de força bruta que eraO(N^2) ouO(N^3), embora tenha produzido resultados corretos. Mas a tarefa especifica:

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

Após algumas pesquisas, pensei que talvez o algoritmo de Kadane pudesse ser modificado para se ajustar a esse problema, mas não o fiz.

Minha pergunta é: o algoritmo de Kadane é o caminho certo a seguir? Caso contrário, você poderia me apontar na direção certa (ou nomear um algoritmo que poderia me ajudar aqui)? Não quero um código pronto, só preciso de ajuda para encontrar o algoritmo certo.