Encontrando a soma absoluta mínima de um subarray
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.