Esse post será puramente teórico, por se tratar de um assunto de uma determinada competição que só se encerra dia primeiro de maio. O código da solução do problema será postado assim que que a competição se encerrar, para não garantir a vantagem de ninguém que, por um acaso, leia o blog.
Vamos falar do problema do apostador. A situação é a seguinte: Temos um apostador que, de alguma forma, sabe exatamente quanto ele ganharia ou perderia no cassino em cada dia. No entanto, ele será banido assim que coletar seus lucros, podendo ficar dentro do cassino quantos dias quiser.
Deseja-se maximizar o lucro nessa situação. Mas como fazer isso de forma que não se precise de muito poder computacional? Poderia-se testar todas as possibilidades: percorrer o vetor que armazena os lucros e perdas com dois vetores (um representando o dia de chegada e um o dia de saida) de tal forma que o período com lucro máximo seja armazenado. Porém essa ideia da forma bruta é da ordem de n! operações, o que dificulta muito quando tem-se um número grande de dias.
Outra ideia seria utilizando uma noção de "ilhas". Contrói-se um ArrayList (ver post anterior) que contém um elemento para cada sequência de dias em que se lucra ou se perde dinheiro. Em seguida, percorre-se a lista fazendo diversos merges em três elementos de cada vez, sempre que compensar (ou seja, sempre que o elemento n+2, que é uma sequência de lucros, tiver valor maior que o elemento n+1, prejuízo, pode-se unir os elementos n, n+1 e n+2). Assim, teremos no final apenas alguns elementos isolados e o maior deles contém o máximo lucro. Porém esse algorítmo é O(n^2). Pode-se melhorar.
A solução final envolve a dependência com o dia anterior. Pode-se dizer que o lucro máximo do dia n será o lucro máximo do dia n-1 mais o lucro (ou prejuízo) do dia n. Se esse valor acumulado em algum momento for negativo, não compensa entrar no cassino até esse dia, e pode-se começar do lucro do zero novamente. Assim é possível percorrer o vetor uma única vez e saber qual o valor máximo de lucro, além do período em que se encontra, que é do dia em que se tem lucro máximo até o primeiro zero anterior a esse dia.
Uma aplicação será mostrada no próxmo post. Até lá!
