Solução Pizza

Solução por Lucca Siaudzionis

Este é um problema conhecido de algoritmos gulosos. Imagine que, em vez de o array que representa a pizza ser cíclico, ele seja linear. Ou seja, temos um array de vários número inteiros e queremos o sub-array de maior soma. Neste caso, mantemos uma variável soma, inicialmente zerada, e percorremos o array, sempre acrescentando o valor da casa que estamos a variável soma. Quando tivermos $$soma < 0$$, resetamos soma para $$soma = 0$$.

Agora, para transformamos esta solução para resolver o problema Pizza, temos que fazer duas alterações:

• duplicar nosso array (“copiando” o mesmo array ao lado do original)
• além de checar se $$soma < 0$$, também precisamos checar se já não acrescentamos mais que $$N$$ valores a variável soma.

O código, então, fica assim:

https://gist.github.com/luccasiau/657c89a7f0ca97256bc4