A melhor compra de ações

URL

https://www.thehuxley.com/problem/410

Comentários

Em uma primeira olhada, esse parece um problema simples de resolver. Realmente, desenvolver uma solução "ingênua" para ele foi o meu primeiro pensamento.

Minha primeira ideia foi para cada preço da ação, ver a diferença para o seguinte e ir guardando o maior encontrado até então. Então eu faria isso para o preço da posição 0, 1, 2, 3 até n.

Basicamente, dois loops aninhandos e resolveria o problema em O (n2) (n ao quadrado).

No problema ele fala que o n pode ser até cem mil. Logo, se realmente existir um caso de teste com 100.000 elementos, eu faria um loop com 10.000.000.000 (dez bilhões) de repetições. Provavelmente isso iria estourar o tempo limite de execução do programa. Mas mesmo assim resolvi tentar. Na maratona, esse é um momento onde você terá que decidir. Se der certo, você economizará alguns bons minutos para se dedicar aos outros problemas. Mas se der errado, você terá perdido vinte minutos no tempo de desempate. Se eu estivesse no seu lugar, eu tentaria primeiro com a solução ineficiente. E só se desse tempo limite excedido, partiria para uma solução mais elaborada e mais demorada para implementar.

Bem, nesse caso o The Huxley não aceitou o meu código e a dica sugeriu que eu deveria fazer o código mais eficiente.

Aí, o que me veio à mente foi a técnica de dividir para conquistar. A ideia seria similar ao merge sort, onde a gente recursivamente quebra o problema em duas partes iguais e depois faz uma combinação do resultado. Como você pode ver no mergesort, essa estratégia (a depender da sua forma de combinar) geralmente é O (n log n), bem melhor que a minha solução quadrática original. Então resolvi seguir por essa linha:

Criei um array somente com as diferenças das cotações
Usei dividir e conquistar, utilizando a técnica de subarray de soma máxima. Em outras palavras, você quebra o array no meio e chama recursivamente a mesma função para cada uma das metades.
O caso base ocorre quando a função é chamada somente com tamanho 1
A ideia é a seguinte: a melhor subsequência ou estará no subarray da esquerda, ou no da direita ou então passando entre os dois;
No caso em que ele passa de um subarray para o outro, a gente pode verificar iniciando a partir do meio e contando para a esquerda e para a direita, procurando a maior sequência encontrada. Esse passo é feito em O (n)
Quando você estiver com os melhores números do lado esquerdo, do direito e do caso onde estaria passando de um para o outro, basta ver qual é o maior.

Tá bem resumido acima, mas é basicamente a mesma lógica do merge sort. Só que no merge sort, a etapa de combinação que nesse exemplo ocorre no procedimento que verifica o caso em que a subsequencia está passando de um array pro outro, no merge sort ocorre o merge dos dois arrays ordenados.

Existe ainda outro algoritmo chamado Kadane, que resolve esse mesmo tipo de problema em O (n) e ainda é mais fácil de implementar. Ele usa um raciocínio de programação dinâmica. Mas se eu tivesse usado ele não iria ilustrar a técnica de dividir e conquistar sendo usada de forma interessante :-)