Solução Pizza

0 Flares Facebook 0 0 Flares ×

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:

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: