Solução por Sofhia Souza
Conhecimento prévio: Programação dinâmica
Chamemos de $$val[]$$ o vetor que guarda o preço das ações em cada dia.
Para este problema, faremos uma dp com dois parâmetros:
- $$u$$: representa o $$u$$-ésimo dia
- $$mod$$: se nesse dia $$u$$ eu já possuo(1) ou não(0) uma ação da empresa
Com isso, teremos que $$dp[u][mod] = max(p1, p2)$$, sendo:
- $$p1$$: caso eu já possua uma ação, irei vendê-la, logo $$p1 = val[u] + dp[u+1][0]$$. Caso eu não possua, irei comprá-la. Então $$p1 = – val[u] – c + dp[u+1][1]$$, pois tenho que pagar o valor da ação e o valor $$c$$ fixo.
- $$p2$$: não faço nada nesse dia, então $$p2 = dp[u+1][mod]$$.
No fim, basta imprimirmos a resposta de $$dp[1][0]$$. Segue o código para melhor entendimento:
https://gist.github.com/sofhiasouza/bc810edf31014a3998df9013530dccbc