Programação dinâmica – Analisando lucro de ações

Olá meu caro leitor,

Seja bem vindo ao nosso conteúdo exclusivo, o TechTrevistas!

Hoje, vamos começar o bate papo de desafios com um desafio de programação dinâmica bem interessante!

O problema consiste em achar as melhores horas para comprar e vender uma ação dado um array de preços e calcular o maior lucro para esse tipo de operação.

O problema tem como premissas:

  • Você só pode vender a ação se você já tiver ela em sua carteira
  • Você só pode realizar duas operações, uma de compra e uma de venda

Alguns exemplos

Input: [7,1,5,3,6,4]
Output: 5
Explicação: Este valor acontece quando compramos a ação no 2o dia e a vendemos no 5o dia (6 - 1)
Input: [7,6,4,3,1]
Output: 0
Explicação: Neste caso, não há nenhuma operação que possa ser feita que dê lucro.

O que diabos é programação dinâmica?

Programação Dinâmica é uma técnica que reduz o problema total a diversos subproblemas, e permite a diminuição de tempo computacional gasto em subproblemas já explorados.

E como a gente aplica nesse problema?

Nesse problema, a programação dinâmica ajudará a gente a reduzir tempo gasto quando:

  • Não tivermos nenhum preço da ação (retornando 0, ou uma exceção)
  • Calculando o maior lucro reduzindo o número de sub problemas a serem analisados

Começando a resolver o problema

Basicamente para começarmos a resolver esse problema, devemos começar escrevendo alguns casos de teste:

from .acoes import checa_lucro
from unittest import TestCase

class TesteAcoes(TestCase):
    def teste_se_array_vazio_retorna_0(self):
        array = []
        assert checa_lucro(array) = 0

    def teste_se_array_com_o_mesmo_valor_retorna_0(self):
        array = [1,1,1,1]
        assert checa_lucro(array) = 0

    def teste_se_array_com_o_maior_valor_retorna_0(self):
        array = [6,1,1,1]
        assert checa_lucro(array) = 0

    def teste_se_array_com_o_lucro_1_retorna_valor_correto(self):
        array = [1,2,6,5]
        assert checa_lucro(array) = 5

    def teste_se_array_com_o_lucro_2_retorna_valor_correto(self):
        array = [1,2,6,7]
        assert checa_lucro(array) = 6

Então, utilizando baby steps, vamos iterar sobre o problema desenvolvendo o protótipo da função com os casos mais simples: o caso do array estar vazio; só conter um item no array; ou conter um item repetido N vezes no array.

def checa_lucro(precos: list) -> int:
    if len(precos) == 0:
        return 0

    if len(set(precos)) == 1:
        return 0

    return 1

Rodando os testes:

$ python -m unittest
FFF..

O resultado dos nossos testes foi:

  • Array vazio retorna 0 – passou
  • Array com todos os itens com o mesmo valor retorna 0 – passou
  • O maior valor está no começo da sequência e não há operações a serem feitas, retornando 0 – não passou
  • Primeira operação com lucro – não passou
  • Segunda operação com lucro – não passou

Agora começa a brincadeira!

Agora que temos o básico testado e pronto para ser usado, podemos pensar na forma de como prosseguirmos para os outros casos de teste!

Supondo um array de preços: [7, 1, 5, 3, 6, 4]

Gráfico do array de preços

Podemos fazer algumas observações interessantes:

  • O maior lucro será o maior valor do período – o menor, sendo que o menor deve ser anterior ao maior
  • Devemos andar pelo array para encontrar as melhores oportunidades
  • O maior lucro no estado inicial é 0, já que no estado inicial não há lucro ainda
  • Assim como o menor preço no estado inicial é maior preço, já que qualquer valor abaixo dele será o menor preço

Com essas premissas, devemos ter um algoritmo que tenha o seguinte comportamento:

  1. Iteração com preço 7 – Menor Preço = 7 e Maior Lucro = 0
  2. Iteração com preço 1 – Menor Preço = 1 e Maior Lucro = 0
  3. Iteração com preço 5 – Menor Preço = 1 e Maior Lucro = 4
  4. Iteração com preço 3 – Menor Preço = 1 e Maior Lucro = 4
  5. Iteração com preço 6 – Menor Preço = 1 e Maior Lucro = 5
  6. Iteração com preço 4 – Menor Preço = 1 e Maior Lucro = 5

Com isso, já podemos começar a esboçar o resto da nossa função:

def checa_lucro(precos: list) -> int:
    if len(precos) == 0:
        return 0

    if len(set(precos)) == 1:
        return 0

    menor_preco = max(precos)
    maior_lucro = 0

    for preco in precos:
        if preco < menor_preco:
            menor_preco = preco

Como discutimos anteriormente, agora, nesta nova função já definimos os valores máximos de lucro e mínimos de preço, além de ir iterando o menor preço até encontrar realmente o valor.

Com esta etapa pronta, faremos o cálculo do maior lucro baseado no menor valor encontrado: O lucro atual deve ser calculado a partir da diferença entre o maior e menor valor encontrado e, para ser o maior lucro, deve ser maior que o maior lucro anterior.

Portanto:

def checa_lucro(precos: list) -> int:
    if len(precos) == 0:
        return 0

    if len(set(precos)) == 1:
        return 0

    menor_preco = max(precos)
    maior_lucro = 0

    for preco in precos:
        if preco < menor_preco:
            menor_preco = preco

        elif (preco - menor_preco > maior_lucro):
            maior_lucro = preco - menor_preco

    return maior_lucro

CHEGAMOS A RESOLUÇÃO

Essa resolução do problema é uma resolução de uma passada, com complexidade temporal de O(n), ou seja, se o array conter X elementos, o algoritmo demorará o tempo proporcional a X elementos.

Também há a possibilidade de resolução via força bruta, ou seja, testando os valores com outros valores (um for dentro de outro for), o que demanda uma complexidade temporal maior, O(nˆ2), como podemos ver abaixo:

def checa_lucro(precos: list) -> int:
    maior_lucro = 0;
    for idx, preco in enumerate(precos):
        for preco_ in precos[idx:]:
            lucro = preco_ - preco 

            if lucro > maior_lucro:
                maior_lucro = lucro

    return maior_lucro

Espero que você tenha curtido essa resolução!